# Implement Magic Dictionary
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/implement-magic-dictionary)
Canonical: https://scaleengineer.com/dsa/problems/implement-magic-dictionary
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Hash Table, String, Trie
---
## Problem
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`.

# Approaches
## Brute Force Comparison
This is the most straightforward and intuitive approach. We don't perform any special pre-processing in `buildDict`. We simply store the dictionary. When `search` is called, we iterate through every word in our stored dictionary and compare it with the `searchWord`. A helper function can be used to check if two words of the same length differ by exactly one character.
**Time:** `buildDict`: O(1) if we only store the reference, or O(D) if we copy the dictionary strings.
`search`: O(N * L), where N is the number of words in the dictionary and L is the length of the `searchWord`. This is because we iterate through all N words and each comparison takes O(L) time. · **Space:** O(D), where D is the total number of characters in all words in the dictionary, to store the dictionary itself.
**Pros:** Very simple to understand and implement.; Minimal time and space complexity for the `buildDict` operation.
**Cons:** The `search` operation is inefficient, with a time complexity proportional to the total size of the dictionary.; For large dictionaries, the search time can be prohibitive, although it passes within the given constraints.
### Explanation
The `buildDict` method takes the array of strings and stores it, for instance, in a `String[]` or `List<String>`. The main logic resides in the `search` method. It performs a linear scan over all the words in the dictionary. For each dictionary word, it first checks if its length matches the `searchWord`'s length. If they don't match, it's impossible for them to be one edit away, so we move to the next word. If the lengths are equal, we proceed to count the number of positions at which their characters differ. If this count is exactly one, we've found our 'magic' word and can immediately return `true`. If we iterate through the entire dictionary without finding such a word, we return `false`.

```java
class MagicDictionary {
    private String[] dictionary;

    public MagicDictionary() {
    }

    public void buildDict(String[] dictionary) {
        this.dictionary = dictionary;
    }

    public boolean search(String searchWord) {
        for (String word : dictionary) {
            if (word.length() != searchWord.length()) {
                continue;
            }
            int diff = 0;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) != searchWord.charAt(i)) {
                    diff++;
                }
            }
            if (diff == 1) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- In the `buildDict` method, simply store the provided `dictionary` array in a member variable.
- In the `search(searchWord)` method:
  - Iterate through each `word` in the stored dictionary.
  - If the length of `word` is different from `searchWord`, skip to the next word.
  - If the lengths are the same, initialize a difference counter to zero.
  - Compare `word` and `searchWord` character by character.
  - For each position where the characters do not match, increment the difference counter.
  - After comparing all characters, if the difference counter is exactly 1, a match is found, so return `true`.
  - If the loop completes without finding any word with exactly one difference, return `false`.

## Grouping by Word Length
This approach is an optimization over the naive brute-force method. The key idea is that a 'magic' match can only exist between words of the same length. We can leverage this by pre-processing the dictionary in `buildDict` to group words by their length. A HashMap is a suitable data structure for this, mapping a word length (Integer) to a list of words of that length.
**Time:** `buildDict`: O(D), as we iterate through all characters of the dictionary once to build the map.
`search`: O(K * L), where K is the number of words with the same length as `searchWord`, and L is the length. This is better than O(N * L) on average but has the same worst-case complexity. · **Space:** O(D), where D is the total number of characters in the dictionary, to store the HashMap.
**Pros:** Improves the average-case performance of `search` by reducing the number of words to compare against.; Still relatively simple to implement.
**Cons:** The worst-case time complexity for `search` is the same as the brute-force approach (when all dictionary words have the same length).; Requires more space and pre-processing time in `buildDict` compared to the simple brute-force approach.
### Explanation
During the `buildDict` phase, we iterate through the dictionary and populate a `HashMap<Integer, List<String>>`. For each word, we use its length as the key and add the word to the list of words for that key. When `search(searchWord)` is called, we first determine the length of `searchWord`. Then, we use this length to directly access the list of all dictionary words that have the same length. This narrows down our search space significantly. We then iterate only over this smaller list of candidates, performing the same one-difference check as in the brute-force approach. If no words of the given length exist in our map, we can immediately return `false`.

```java
class MagicDictionary {
    private Map<Integer, List<String>> map;

    public MagicDictionary() {
        map = new HashMap<>();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            int len = word.length();
            map.computeIfAbsent(len, k -> new ArrayList<>()).add(word);
        }
    }

    public boolean search(String searchWord) {
        int len = searchWord.length();
        if (!map.containsKey(len)) {
            return false;
        }
        for (String word : map.get(len)) {
            int diff = 0;
            for (int i = 0; i < len; i++) {
                if (word.charAt(i) != searchWord.charAt(i)) {
                    diff++;
                }
            }
            if (diff == 1) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- In `buildDict`, initialize a `HashMap<Integer, List<String>>`.
- Iterate through each `word` in the input `dictionary`.
- For each `word`, get its length and add it to the list associated with that length in the HashMap.
- In `search(searchWord)`:
  - Get the length of `searchWord`, say `len`.
  - Retrieve the list of candidate words from the HashMap using `len` as the key.
  - If no list exists for that key, return `false`.
  - Iterate through the retrieved list of candidate words.
  - For each candidate, count the character differences with `searchWord`.
  - If the difference count is exactly 1, return `true`.
  - If the loop finishes, return `false`.

## Hashing with Generalized Words
This approach trades off a slower, more memory-intensive `buildDict` phase for a much faster `search` operation. The core idea is to pre-compute all possible one-character variations of the dictionary words. We do this by creating 'generalized' words. For example, for the word "hello", we generate patterns like "*ello", "h*llo", "he*lo", etc. We store these patterns in a HashMap and count how many dictionary words map to each pattern.
**Time:** `buildDict`: O(N * L^2). For each of the N words, we generate L patterns, and each pattern generation takes O(L) time due to string manipulations.
`search`: O(L^2). We generate L patterns for the `searchWord`, and each generation and lookup takes O(L) time. · **Space:** O(N * L^2), where N is the number of words and L is their maximum length. This is because we can have up to N*L generalized words, each of length L.
**Pros:** Extremely fast `search` operation, with a time complexity that depends only on the length of the word, not the size of the dictionary.; This is the most efficient approach when `search` is called many times.
**Cons:** The `buildDict` method is significantly more complex and time-consuming.; Requires a large amount of space to store all the generalized word patterns, O(N * L^2).
### Explanation
In `buildDict`, we process each word from the dictionary. For a word of length L, we generate L different patterns by replacing each character, one by one, with a wildcard like '*'. We store these patterns as keys in a HashMap, and their values are the counts of how many dictionary words generate that specific pattern. We also store the original dictionary words in a HashSet for quick lookups.

When `search(searchWord)` is called, we apply the same generalization process. For each position in `searchWord`, we create a pattern and look it up in our HashMap. If the pattern exists, we check its count. 
- If the count is greater than 1, it means at least two words in the dictionary match this pattern. Even if `searchWord` itself is one of them, there's at least one other, so we have a valid magic match. 
- If the count is exactly 1, we must ensure the single dictionary word that matches this pattern is not `searchWord` itself (as we need to change a character). We can verify this by checking if `searchWord` exists in our original dictionary HashSet. If it doesn't, the match is valid.

```java
class MagicDictionary {
    private Set<String> words;
    private Map<String, Integer> counts;

    public MagicDictionary() {
        words = new HashSet<>();
        counts = new HashMap<>();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            this.words.add(word);
            for (int i = 0; i < word.length(); i++) {
                String pattern = word.substring(0, i) + "*" + word.substring(i + 1);
                counts.put(pattern, counts.getOrDefault(pattern, 0) + 1);
            }
        }
    }

    public boolean search(String searchWord) {
        for (int i = 0; i < searchWord.length(); i++) {
            String pattern = searchWord.substring(0, i) + "*" + searchWord.substring(i + 1);
            int count = counts.getOrDefault(pattern, 0);
            if (count > 1 || (count == 1 && !words.contains(searchWord))) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- In `buildDict`:
  - Initialize a `HashMap<String, Integer> counts` and a `HashSet<String> words`.
  - For each `word` in the `dictionary`:
    - Add `word` to the `words` set.
    - For each character position `i` in `word`, create a generalized pattern by replacing the character at `i` with a wildcard (e.g., '*').
    - Increment the count for this pattern in the `counts` map.
- In `search(searchWord)`:
  - For each character position `i` in `searchWord`, create a generalized pattern.
  - Look up this pattern in the `counts` map to get its frequency, `count`.
  - A match is found if `count > 1`.
  - A match is also found if `count == 1` AND `searchWord` is not in the original `words` set.
  - If a match is found, return `true`.
  - If the loop finishes, return `false`.

# Solutions
### Java

```java
class Trie { private Trie [] children = new Trie [ 26 ]; private boolean isEnd ; public void insert ( String w ) { Trie node = this ; for ( char c : w . toCharArray ()) { int i = c - 'a' ; if ( node . children [ i ] == null ) { node . children [ i ] = new Trie (); } node = node . children [ i ]; } node . isEnd = true ; } public boolean search ( String w ) { return dfs ( w , 0 , this , 0 ); } private boolean dfs ( String w , int i , Trie node , int diff ) { if ( i == w . length ()) { return diff == 1 && node . isEnd ; } int j = w . charAt ( i ) - 'a' ; if ( node . children [ j ] != null ) { if ( dfs ( w , i + 1 , node . children [ j ], diff )) { return true ; } } if ( diff == 0 ) { for ( int k = 0 ; k < 26 ; k ++) { if ( k != j && node . children [ k ] != null ) { if ( dfs ( w , i + 1 , node . children [ k ], 1 )) { return true ; } } } } return false ; } } class MagicDictionary { private Trie trie = new Trie (); public MagicDictionary () { } public void buildDict ( String [] dictionary ) { for ( String w : dictionary ) { trie . insert ( w ); } } public boolean search ( String searchWord ) { return trie . search ( searchWord ); } } /** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary obj = new MagicDictionary(); * obj.buildDict(dictionary); * boolean param_2 = obj.search(searchWord); */
```

### CPP

```cpp
class Trie { private: Trie * children [ 26 ]; bool isEnd = false ; public: Trie () { fill ( begin ( children ), end ( children ), nullptr ); } void insert ( const string & w ) { Trie * node = this ; for ( char c : w ) { int i = c - 'a' ; if ( ! node -> children [ i ]) { node -> children [ i ] = new Trie (); } node = node -> children [ i ]; } node -> isEnd = true ; } bool search ( const string & w ) { function < bool ( int , Trie * , int ) > dfs = [ & ]( int i , Trie * node , int diff ) { if ( i >= w . size ()) { return diff == 1 && node -> isEnd ; } int j = w [ i ] - 'a' ; if ( node -> children [ j ] && dfs ( i + 1 , node -> children [ j ], diff )) { return true ; } if ( diff == 0 ) { for ( int k = 0 ; k < 26 ; ++ k ) { if ( k != j && node -> children [ k ]) { if ( dfs ( i + 1 , node -> children [ k ], 1 )) { return true ; } } } } return false ; }; return dfs ( 0 , this , 0 ); } }; class MagicDictionary { public: MagicDictionary () { trie = new Trie (); } void buildDict ( vector < string > dictionary ) { for ( auto & w : dictionary ) { trie -> insert ( w ); } } bool search ( string searchWord ) { return trie -> search ( searchWord ); } private: Trie * trie ; }; /** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary* obj = new MagicDictionary(); * obj->buildDict(dictionary); * bool param_2 = obj->search(searchWord); */
```

### Python

```python
class Trie : __slots__ = [ "children" , "is_end" ] def __init__ ( self ): self . children = {} self . is_end = False def insert ( self , w : str ) -> None : node = self for c in w : if c not in node . children : node . children [ c ] = Trie () node = node . children [ c ] node . is_end = True def search ( self , w : str ) -> bool : def dfs ( i : int , node : Trie , diff : int ) -> bool : if i == len ( w ): return diff == 1 and node . is_end if w [ i ] in node . children and dfs ( i + 1 , node . children [ w [ i ]], diff ): return True return diff == 0 and any ( dfs ( i + 1 , node . children [ c ], 1 ) for c in node . children if c != w [ i ] ) return dfs ( 0 , self , 0 ) class MagicDictionary : def __init__ ( self ): self . trie = Trie () def buildDict ( self , dictionary : List [ str ]) -> None : for w in dictionary : self . trie . insert ( w ) def search ( self , searchWord : str ) -> bool : return self . trie . search ( searchWord ) # Your MagicDictionary object will be instantiated and called as such: # obj = MagicDictionary() # obj.buildDict(dictionary) # param_2 = obj.search(searchWord)
```