676. Implement Magic Dictionary

Tags: ‘Hash Table’, ‘Trie’

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.

For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Note:

You may assume that all the inputs are consist of lowercase letters a-z.
For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

Solution

方法1 Build a Trie for searching. 把每一位i的字符替换成a-z其他字符，然后搜索，如果搜到了就return true。

假设字典word平均长度为a，搜索字符长度为N. Trie insert search均为 O(a)

所以buildDict()为O(字典总长度)，search()为O(24*a*N)

O(a) O(24aN) 9% 100%

class MagicDictionary {
    private Trie trie;
    private class Node {
        private Node[] children;
        private boolean isWord;
        private Node() {
            this.children = new Node[26];
        }
    }
    
    private class Trie {
        private Node root;
        private Trie() {
            this.root = new Node();
        }
        
        private void insert(String word) {
            Node p = root;
            for (int i = 0; i < word.length(); i++) {
                int index = (int)(word.charAt(i) - 'a');
                if (p.children[index] == null) {
                    p.children[index] = new Node();
                }
                p = p.children[index];
            }
            p.isWord = true;
        }
        
        private boolean search(String word) {
            Node p = root;
            for (int i = 0; i < word.length(); i++) {
                int index = (int)(word.charAt(i) - 'a');
                if (p.children[index] == null) {
                    return false;
                }
                p = p.children[index];
            }
            return p != null && p.isWord;
        }
    }
    
    public MagicDictionary() {
         this.trie = new Trie();
    }

    public void buildDict(String[] dict) {
        for (String word: dict) {
            trie.insert(word);
        }
    }
    
    public boolean search(String word) {
        for (int i = 0; i < word.length(); i++) {
            char o = word.charAt(i);
            for (char n = 'a'; n <= 'z'; n++) {
                if (n == o) {
                    continue;
                }
                String newWord = word.substring(0, i) + n + word.substring(i+1);
                if (trie.search(newWord)) {
                    return true;
                }
            }
            
        }
        return false;
    }
}

方法2：可以只借鉴前缀树的思路，单纯用一个set存储，search可以降为O(1) 总体search复杂度为O(24*N) 12% 100%

class MagicDictionary {
    private Set<String> set;
    
    public MagicDictionary() {
         this.set = new HashSet<String>();
    }
    
    public void buildDict(String[] dict) {
        for (String word: dict) {
            set.add(word);
        }
    }
    
    public boolean search(String word) {
        for (int i = 0; i < word.length(); i++) {
            char o = word.charAt(i); // 0 -> old char
            for (char n = 'a'; n <= 'z'; n++) { // n -> new char
                if (n == o) {
                    continue;
                }
                String newWord = word.substring(0, i) + n + word.substring(i+1);
                if (set.contains(newWord)) {
                    return true;
                }
            }
            
        }
        return false;
    }
}

Alex Blog

676. Implement Magic Dictionary