In this article we are going to discuss a famous Leetcode medium level problem called "Implement Magic Dictionary" problem. This will involve the concept of Hash Table/ Map and Tries.

Table of Contents:

1. Question
2. Example
3. Given Constraints
4. Explanation
5. Logic
6. Implementing Code
   • Approach 1: Brute Force (comparing each string one by one)
   • Approach 2 : Using Hash Table in Java
   • Approach 3 : Using tries in Java
7. Time and Space Complexity
8. Conclusion

Question

Implement a magic dictionary data structure with methods:

• buildDict
• search

For the method buildDict, we will be given a list of different words to build a dictionary.

For this method search, a word will be given and we have to find whether if we can modify exactly one character into another character in this word such that the modified word is in the dictionary.

Example

Input
["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["enjoy","maths"]], ["enjoy"], ["ennjoy"], ["enjo"], ["secret"]]
Output
[null,null,false,false,false,false]

Explanation
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(["enjoy","maths""]);
magicDictionary.search("enjoy"); // return False
magicDictionary.search("ennjoy"); // return false
magicDictionary.search("enjo"); // return False
magicDictionary.search("secret"); // return False

Given 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.

Explanation

Implement a new data structure called magic directory with buildDict, and **search **methods.

For the method buildDict, we will be given a list of non-repetitive words to build a dictionary.

For the method search, we have been given a word, and find whether if we modify exactly one character into another character in this word, the modified word is present in the dictionary we just built.

Logic

• Convert dictionary list to hashmap
• m = { len(word): [words]}
• Given searchWord, check if m has key of len(searchWord) => wordList
• For every word in wordList, check if there's a word that is one letter different from searchWord

Implementing Code

Approach 1: Brute Force (comparing each string one by one)

Explanation:
Before we start with this naive approach we need to understand two things before proceeding with this approach:-

1. Strings can only be same if their lengths are equal.
2. Call two strings same if exactly one character can be changed in one to make the strings equal.

So, when searching a new word, let's check only the words that are the same length. Since the search asks us to return true only when we change one character and find a match in dictionary we have built. We can use an unordered hashset. So we can make a frequency map that needs to match in length except for one spot needs to be the difference of exactly one character. If the above condition does not satisfy we return false, i.e., the word is not in the dictionary. Otherwise its a match and return true.

Now, lets implement this code in java language.

class MagicDictionary {
    Map<Integer, List<String>> bucket;

    /** Initialize your data structure here. */
    public MagicDictionary() {
        bucket = new HashMap<>();
    }

    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String word : dict) {
            bucket.computeIfAbsent(word.length(), x -> new ArrayList<>()).add(word);
        }
    }

    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    public boolean search(String word) {
        if (!bucket.containsKey(word.length())) {
            return false;
        }

        for (String s : bucket.get(word.length())) {
            int misMatch = 0;
            for (int i = 0; i < word.length(); i++) {
                if (s.charAt(i) != word.charAt(i)) {
                    if (++misMatch > 1) {
                        break;
                    }
                }
            }
            if (misMatch == 1) {
                return true;
            }
        }

        return false;
    }
}

TIME AND SPACE COMPLEXITY
Time Complexity:
buildDict: O(S)
search: O(N*K)

Space Complexity:O(S)

where,
S: total letter count, N: dict length, K: length of the word to be searched

Approach 2 : Using Hash Table in Java

Algorithm :
Step 1 : Simply constructing a hash map with length of the word can reduce the search frequency in ideal case.

Step 2 : Add all dictionary words to HashMap with length of string as the key and set of words as value.
e.g.: "hello" -> {"ello":[[0, 'h']], "hllo":[[1, 'e']], "helo":[[2, 'l'],[3, 'l']], "hell":[[4, 'o']]}

Step 3 : For searching, check if the given word length is available in map - if not return false;

Step 4 : If available, count the character mismatch. If character mismatch is more than one, go to next word in dictionary of same length.

Step 5 : If mismatch count is exactly one, that means our word will be counted as part of the dictionary. So return true.

class MagicDictionary {

    Map<String, List<int[]>> map = new HashMap<>();
    /** Initialize your data structure here. */
    public MagicDictionary() {
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String s : dict) {
            for (int i = 0; i < s.length(); i++) {
                String key = s.substring(0, i) + s.substring(i + 1);
                int[] pair = new int[] {i, s.charAt(i)};
                
                List<int[]> val = map.getOrDefault(key, new ArrayList<int[]>());
                val.add(pair);
                
                map.put(key, val);
            }
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    public boolean search(String word) {
        for (int i = 0; i < word.length(); i++) {
            String key = word.substring(0, i) + word.substring(i + 1);
            if (map.containsKey(key)) {
                for (int[] pair : map.get(key)) {
                    if (pair[0] == i && pair[1] != word.charAt(i)) return true;
                }
            }
        }
        return false;
    }
}

TIME AND SPACE COMPLEXITY
Time Complexity:
**buildDict: O(Σ|dictionary[i]|^2) **
search: O(|searchWord|^2)

Space O(Σ|dictionary[i]|)

Approach 3 : Using tries in Java

Algorithm :
Step 1 : Initialize your data structure here.

Step 2 : Build a dictionary through a list of words. We can use a Trie to efficiently store strings and search them.

Step 3 : We define a TrieNode to use for this algorithm. Every word needs to be added into Trie starting from 'root' so everytime update the curr to root.

Step 4 : Returns if there is any word in the trie that equals to the given word after modifying exactly one character. Then, for each time search is called, we will go through each possible letter at each level to see if we can find a sequence that can match the input string with exactly 1 modification.

Example : if we have two words hello and hallo, sth like

						root-h-e-l-l-o
							  \
								a-l-l-o

Then after the h, we will check both e and a as the next chracter to see if the resulting subsequence can satisfy the condition.

Step 5 : We should check all possible combinations of sequences from our Trie that can match the search word. Everytime we cannot match a character in the search word, we will increment the paramter attempt by 1 and skip that character.

Step 6 : If we can reach the end of the search string with exactly 1 attempt, then we can safely return True

class MagicDictionary {
    class TrieNode {
        char val;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode(char val) {
            this.val = val;
            childNode = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ');
        }

        public void insert(String word) {
            if (word == null || word.length() == 0) {
                return;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (curNode.childNode[index] == null) {
                    curNode.childNode[index] = new TrieNode(c);
                }
                curNode = curNode.childNode[index];
            }
            curNode.isWord = true;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) {
                return false;
            }

            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (curNode.childNode[index] == null) {
                    return false;
                }
                curNode = curNode.childNode[index];
            }
            return curNode.isWord;
        }
    }

    Trie trie;

    public MagicDictionary() {
        trie = new Trie();
    }

    public void buildDict(String[] dict) {
        for (String word : dict) {
            trie.insert(word);
        }
    }

    public boolean search(String word) {
        char[] letters = word.toCharArray();
        for (int i = 0; i < word.length(); i++) {
            char oldC = letters[i];

            for (char c = 'a'; c <= 'z'; c++) {
                if (c == oldC) {
                    continue;
                }

                letters[i] = c;
                String newWord = new String(letters);
                if (trie.search(newWord)) {
                    return true;
                }
            }
            letters[i] = oldC;
        }
        return false;
    }
}

Time Complexity:
buildDict: O(n*m)
where,
n : numbers of words
m : length of word

search: O(m)
where,
m: length of word

Also,
Space Complexity:O(n*m)

Conclusion

Hence we were able to solve the medium level Leetcode problem "Implement Magic Dictionary" using two methods and wrote their code in Java in this article at OpenGenus. We have explored three established solutions:

• Brute Force
• Hashmaps
• Tries