Implement Magic Dictionary

Share

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.

Example 1
buildDict(["hello","world"]), search("hello")ā†’false, search("hhllo")ā†’true, search("hell")ā†’false

Solution Approach

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).
Java
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