Design a data structure that supports buildDict and search. search(word) returns true if the word differs from any dictionary word by exactly one character.
buildDict(["hello","world"]), search("hello")→false, search("hhllo")→true, search("hell")→false
Build a Trie. For search, use DFS allowing exactly one character substitution.
- Insert all words into Trie.
- search(word): DFS through Trie with a "canChange" flag.
- At each position: if chars match, continue with same canChange.
- If chars differ: only continue if canChange=true, setting canChange=false.
- At end: return isEnd AND canChange==false (exactly one change made).
class MagicDictionary {
TrieNode root = new TrieNode();
public void buildDict(String[] dictionary) {
for (String w : dictionary) {
TrieNode node = root;
for (char c : w.toCharArray()) {
if (node.ch[c-'a']==null) node.ch[c-'a'] = new TrieNode();
node = node.ch[c-'a'];
}
node.isEnd = true;
}
}
public boolean search(String searchWord) {
return dfs(root, searchWord, 0, false);
}
private boolean dfs(TrieNode node, String w, int i, boolean changed) {
if (i == w.length()) return changed && node.isEnd;
char c = w.charAt(i);
for (int j = 0; j < 26; j++) {
if (node.ch[j] == null) continue;
boolean diff = (j != c-'a');
if (diff && changed) continue;
if (dfs(node.ch[j], w, i+1, changed || diff)) return true;
}
return false;
}
static class TrieNode { TrieNode[] ch=new TrieNode[26]; boolean isEnd; }
}
- Time Complexity: search: O(L * 26)
- Space Complexity: O(N * L) for Trie