Leetcode--Java--676. 实现一个魔法字典
题目描述
样例描述
思路
字典树 前缀树 trie 暴力做法
- 构建字典树，对于每个字符，枚举修改成a~z，除了本身，看新的字符串是否在trie中存在
代码
class MagicDictionary {
class TrieNode {
TrieNode tns[] = new TrieNode[26];
boolean isWord;
public TrieNode(){
}
}
TrieNode root;
public MagicDictionary() {
root = new TrieNode();
}
public void buildDict(String[] dictionary) {
for (String s: dictionary) {
TrieNode p = root;
for (char c: s.toCharArray()) {
int u = c - a;
if (p.tns[u] == null) {
p.tns[u] = new TrieNode();
}
p = p.tns[u];
}
p.isWord = true;
}
}
public boolean search(String searchWord) {
//先转化为字符数组，方便更改单个字母
char ch[] = searchWord.toCharArray();
for (int i = 0; i < ch.length; i ++ ) {
//对于每一个词，枚举它可能替换的词a~z 除了自己本身
for (char c = a; c <= z; c ++ ) {
if (ch[i] == c) {
continue;
}
//存下原本的
char orgi = ch[i];
ch[i] = c; //替换
//判断替换后的新字符串在trie树上是否存在
if (helper(new String(ch), root)) {
return true;
}
//记得还原，方便后续判断
ch[i] = orgi;
}
}
return false;
}
public boolean helper(String s, TrieNode root) {
TrieNode p = root;
for (char c: s.toCharArray()) {
int u = c - a;
if (p.tns[u] == null) {
return false;
}
p = p.tns[u];
}
return p.isWord;
}
}
/**
* Your MagicDictionary object will be instantiated and called as such:
* MagicDictionary obj = new MagicDictionary();
* obj.buildDict(dictionary);
* boolean param_2 = obj.search(searchWord);
*/
