Implement Magic Dictionary

Design a data structure that is initialized with a list of different words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Implement the MagicDictionary class:

• MagicDictionary() Initializes the object.
• void buildDict(String[] dictionary) Sets the data structure with an array of distinct strings dictionary.
• bool search(String searchWord) Returns true if you can change exactly one character in searchWord to match any string in the data structure, otherwise returns false.

Example 1:

Input [“MagicDictionary”, “buildDict”, “search”, “search”, “search”, “search”] [[], [[“hello”, “leetcode”]], [“hello”], [“hhllo”], [“hell”], [“leetcoded”]] Output [null, null, false, true, false, false]

Explanation MagicDictionary magicDictionary = new MagicDictionary(); magicDictionary.buildDict([“hello”, “leetcode”]); magicDictionary.search(“hello”); // return False magicDictionary.search(“hhllo”); // We can change the second ‘h’ to ‘e’ to match “hello” so we return True magicDictionary.search(“hell”); // return False magicDictionary.search(“leetcoded”); // return False

Constraints:

• 1 <= dictionary.length <= 100
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case English letters.
• All the strings in dictionary are distinct.
• 1 <= searchWord.length <= 100
• searchWord consists of only lower-case English letters.
• buildDict will be called only once before search.
• At most 100 calls will be made to search.

Approach: Trie with Allowed Mismatch Count

Algorithm

1. Insert all dictionary words into a trie
2. For search, traverse the trie while allowing exactly one mismatch:

• If the characters match, follow the child and recurse with the same mismatch budget
• If they differ and a mismatch is still allowed, try every other child and consume the budget

3. A match requires reaching a word end with exactly one mismatch consumed

Time & Space Complexity

• Time Complexity: O(L) expected for search with a small branching factor at the single mismatch; worst case O(26 * L)
• Space Complexity: O(N * L) - the trie nodes for the dictionary

Java Implementation

public class MagicDictionary {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    private final TrieNode root;

    public MagicDictionary() {
        root = new TrieNode();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }
    }

    public boolean search(String searchWord) {
        return search(root, searchWord, 0, true);
    }

    private boolean search(TrieNode node, String word, int pos, boolean canMismatch) {
        if (node == null) {
            return false;
        }
        if (pos == word.length()) {
            return node.isEnd && !canMismatch;
        }

        char c = word.charAt(pos);
        if (node.children[c - 'a'] != null) {
            if (search(node.children[c - 'a'], word, pos + 1, canMismatch)) {
                return true;
            }
        }

        if (canMismatch) {
            for (int i = 0; i < 26; i++) {
                if (i != c - 'a' && node.children[i] != null) {
                    if (search(node.children[i], word, pos + 1, false)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    // Test method
    public static void main(String[] args) {
        MagicDictionary magicDictionary = new MagicDictionary();
        magicDictionary.buildDict(new String[]{"hello", "leetcode"});
        System.out.println(magicDictionary.search("hello"));    // return false
        System.out.println(magicDictionary.search("hhllo"));    // return true
        System.out.println(magicDictionary.search("hell"));     // return false
        System.out.println(magicDictionary.search("leetcoded")); // return false
    }
}

Example Walkthrough

With dictionary [“hello”, “leetcode”]:

1. search("hello"): follows h-e-l-l-o to a word end, but canMismatch is still true (zero mismatches used) -> false
2. search("hhllo"): at position 1, ‘h’ != ‘e’, consumes the mismatch and matches “hello” -> true
3. search("hell"): reaches the end of the trie path before consuming a mismatch, and no word of length 4 ends at a node -> false
4. search("leetcoded"): the path for “leetcoded” breaks and the mismatch budget cannot fix the extra characters -> false

Key Points

1. Exactly One Change: Zero changes must fail, and more than one must fail
2. Mismatch Budget: A boolean canMismatch tracks whether the single allowed change is still available
3. Word End Requirement: A candidate matches only when a trie word ends at the same position
4. Same-Length Restriction: Prefixes of different lengths (like “hell”) automatically fail
5. Branching at Mismatch: When a mismatch is allowed, try all 25 other letters before giving up