LeetCode 676 - Implement Magic Dictionary


https://leetcode.com/problems/implement-magic-dictionary/description/
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:
  1. You may assume that all the inputs are consist of lowercase letters a-z.
  2. For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
  3. 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.


X.
// len->
private Map<Integer, TreeSet<String>> 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 word : dict) {
map.computeIfAbsent(word.length(), li -> new TreeSet<>()).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 (!map.containsKey(word.length())) {
return false;
}

TreeSet<String> set = map.get(word.length());
// <
String floor = set.lower(word);
char[] charArray = word.toCharArray();
if (floor != null && isDistanceOne(charArray, floor.toCharArray())) {
return true;
}

// >
String ceil = set.higher(word);
if (ceil != null && isDistanceOne(charArray, ceil.toCharArray())) {
return true;
}
return false;
}

// hello, hello should return false;
private boolean isDistanceOne(char[] word1, char[] word2) {
if (word1.length != word2.length)
return false;
int diff = 0;

for (int i = 0; i < word1.length; i++) {
if (word1[i] != word2[i]) {
diff++;
if (diff >= 2)
return false;
}
}
// BUG: not return true;
return diff == 1;

}

X. Using Trie

X. Trie
https://leetcode.com/problems/implement-magic-dictionary/discuss/177342/66ms-Prefix-Tree-(Trie)-Java-with-Explanation
We could build a trie using word in dicts. If two words differ by one character only, they will be within the branches regardless of the mismatched character.
For example, dict = ["ooo", "ooa"] and search("oxo"), they have one character mismatched, 

o - o [mismatched here, cntMismatched = 1] - a [mismatched here, cntMismatched = 2, backtrack]
               - o - exhausted [cntMismatched = 1, return true]

    private static Node root;
    public MagicDictionary() {
        root = new Node();       
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        buildTrie(dict);
    }
    
    private void buildTrie(String[] dict) {
        Node ptr;
        for (String word : dict) {
            ptr = root;
            for (char ch : word.toCharArray()) {
                int order = ch - 'a';
                if (ptr.children[order] == null)
                    ptr.children[order] = new Node();
                ptr = ptr.children[order];
            }
            ptr.isWordEnd = true;
        }
    }
    
    /** 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) {        
        return dfs(0, word, root, 0);
    }
    
    private boolean dfs(int curId, String word, Node parentPtr, int cntMismatched) {
        
        if (cntMismatched > 1) {
            return false;
        }
        
        if (curId == word.length()) {       
            return parentPtr.isWordEnd && cntMismatched == 1;
        }

        
        for (int i = 0; i < 26; i++) {          
            int order = word.charAt(curId) - 'a';
            if (parentPtr.children[i] == null)
                continue;       
            if (order != i) {
                if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched + 1))
                    return true;
            } else {
                if (dfs(curId + 1, word, parentPtr.children[i], cntMismatched))
                    return true;
            }
        }     
       
        return false;
    }
    
    class Node {
        
        Node[] children;
        boolean isWordEnd;
        
        public Node() {
            children = new Node[26];
            isWordEnd = false;
        }
    }
https://leetcode.com/problems/implement-magic-dictionary/discuss/107457/Java-implementation-using-Trie
This solution beats 93.56% java solutions.
https://leetcode.com/problems/implement-magic-dictionary/discuss/107465/Efficient-Trie-and-Java-8-w-Explanation
        Trie trie;
        public MagicDictionary() {
            trie = new Trie(256);
        }

        public void buildDict(String[] dict) {
            Arrays.stream(dict).forEach(s -> trie.insert(s));
        }

        public boolean search(String word) {
            return trie.relaxedSearch(word);
        }

        class Trie {
            private int R;
            private TrieNode root;

            public Trie(int R) {
                this.R = R;
                root = new TrieNode();
            }
            
            public boolean relaxedSearch(String word) {
                return relaxedSearch(root, word, 0);
            }

            private boolean relaxedSearch(TrieNode root, String word, int changedTimes) {
                if (root == null || (!root.isWord && word.isEmpty()) || changedTimes > 1) return false;
                if (root.isWord && word.isEmpty()) return changedTimes == 1;
                return Arrays.stream(root.next).anyMatch(nextNode -> relaxedSearch(nextNode, word.substring(1),
                        root.next[word.charAt(0)] == nextNode ? changedTimes : changedTimes+1));
            }

            // Inserts a word into the trie.
            public void insert(String word) {
                insert(root, word);
            }

            private void insert(TrieNode root, String word) {
                if (word.isEmpty()) { root.isWord = true; return; }
                if (root.next[word.charAt(0)] == null) root.next[word.charAt(0)] = new TrieNode();
                insert(root.next[word.charAt(0)], word.substring(1));
            }

            private class TrieNode {
                private TrieNode[] next = new TrieNode[R];
                private boolean isWord;
            }

        }
https://leetcode.com/problems/implement-magic-dictionary/discuss/107453/Easiest-JAVA-with-Trie-no-need-to-count-the-number-of-changes
First build a trie tree, and in search(String word) function, we just edit every character from 'a' to 'z' and search the new string.
(This process is like "word ladder")


if k is the average length of input string, you are using O(nk) for building the Trie and O(26k^2) for searching the Trie.. That's a really bad application for Trie.
If you really want to iterate all 26 alphabet possibilities (which is unnecessary), why don't you just use a HashSet. so O(n) for building the set and O(26k) for searching?

 By changing every character and then search in Trie, the advantage of the Trie is completely lost, maybe even worst than use a set. @bianhit 's implementation takes the advantage of Trie.

 if k is the average length of input string, you are using O(nk) for building the Trie and O(26k^2) for searching the Trie.. That's a really bad application for Trie.
If you really want to iterate all 26 alphabet possibilities (which is unnecessary), why don't you just use a HashSet. so O(n) for building the set and O(26k) for searching?

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
        public TrieNode() {}
    }
    TrieNode root;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        root = new TrieNode();
    }
    
    /** Build a dictionary through a list of words */
    public void buildDict(String[] dict) {
        for (String s : dict) {
            TrieNode node = root;
            for (char c : s.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
    }
    
    /** 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) {
        char[] arr = word.toCharArray();
        for (int i = 0; i < word.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (arr[i] == c) {
                    continue;
                }
                char org = arr[i];
                arr[i] = c;
                if (helper(new String(arr), root)) {
                    return true;
                }
                arr[i] = org;
            }
        }
        return false;
    }
    public boolean helper(String s, TrieNode root) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                return false;
            }
            node = node.children[c - 'a'];
        }
        return node.isWord;
    }
X. Approach #2: Generalized Neighbors [Accepted]
Let's say a word 'apple' has generalized neighbors '*pple', 'a*ple', 'ap*le', 'app*e', and 'appl*'. When searching for whether a word like 'apply' has a neighbor like 'apple', we only need to know whether they have a common generalized neighbor.
Continuing the above thinking, one issue is that 'apply' is not a neighbor with itself, yet it has the same generalized neighbor '*pply'. To remedy this, we'll count how many sources generated '*pply'. If there are 2 or more, then one of them won't be 'apply'. If there is exactly one, we should check that it wasn't 'apply'. In either case, we can be sure that there was some magic word generating '*pply' that wasn't 'apply'.
  • Time Complexity: O(\sum w_i^2) to build and O(K^2) to search, where w_i is the length of words[i], and K is the length of our search word.
  • Space Complexity: O(\sum w_i^2), the space used by count. We also use O(K^2) space when generating neighbors to search.
    Set<String> words;
    Map<String, Integer> count;

    public MagicDictionary() {
        words = new HashSet();
        count = new HashMap();
    }

    private ArrayList<String> generalizedNeighbors(String word) {
        ArrayList<String> ans = new ArrayList();
        char[] ca = word.toCharArray();
        for (int i = 0; i < word.length(); ++i) {
            char letter = ca[i];
            ca[i] = '*';
            String magic = new String(ca);
            ans.add(magic);
            ca[i] = letter;
        }
        return ans;
    }

    public void buildDict(String[] words) {
        for (String word: words) {
            this.words.add(word);
            for (String nei: generalizedNeighbors(word)) {
                count.put(nei, count.getOrDefault(nei, 0) + 1);
            }
        }
    }

    public boolean search(String word) {
        for (String nei: generalizedNeighbors(word)) {
            int c = count.getOrDefault(nei, 0);
            if (c > 1 || c == 1 && !words.contains(word)) return true;
        }
        return false;
    }
只不过这道题的两个单词之间长度必须相等。所以只需检测和要搜索单词长度一样的单词即可，所以我们用的数据结构就是根据单词的长度来分，把长度相同相同的单词放到一起，这样就可以减少搜索量。那么对于和要搜索单词进行比较的单词，由于已经保证了长度相等，我们直接进行逐个字符比较即可，用cnt表示不同字符的个数，初始化为0。如果当前遍历到的字符相等，则continue；如果当前遍历到的字符不相同，并且此时cnt已经为1了，则break，否则cnt就自增1。退出循环后，我们检测是否所有字符都比较完了且cnt为1，是的话则返回true，否则就是跟下一个词比较。如果所有词都比较完了，则返回false
https://leetcode.com/articles/implement-magic-dictionary/
Approach #1: Brute Force with Bucket-By-Length [Accepted]

  • Time Complexity: O(S) to build and O(NK) to search, where N is the number of words in our magic dictionary, S is the total number of letters in it, and K is the length of the search word.
  • Space Complexity: O(S), the space used by buckets.
class MagicDictionary {
    Map<Integer, ArrayList<String>> buckets;
    public MagicDictionary() {
        buckets = new HashMap();
    }

    public void buildDict(String[] words) {
        for (String word: words) {
            buckets.computeIfAbsent(word.length(), x -> new ArrayList()).add(word);
        }
    }

    public boolean search(String word) {
        if (!buckets.containsKey(word.length())) return false;
        for (String candidate: buckets.get(word.length())) {
            int mismatch = 0;
            for (int i = 0; i < word.length(); ++i) {
                if (word.charAt(i) != candidate.charAt(i)) {
                    if (++mismatch > 1) break;
                }
            }
            if (mismatch == 1) return true;
        }
        return false;
    }

https://zxi.mytechroad.com/blog/hashtable/leetcode-676-implement-magic-dictionary/
    MagicDictionary() {
        dict_.clear();
    }
    
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for(string& word: dict) {
            for(int i = 0; i < word.length(); ++i) {
                char c = word[i];
                word[i] = '*';
                dict_[word].insert(c);
                word[i] = c;
            }
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        for(int i = 0; i < word.length(); ++i) {
            char c = word[i];
            word[i] = '*';
            if (dict_.count(word)) {
                const auto& char_set = dict_[word];
                if (!char_set.count(c) || char_set.size() > 1)
                    return true;
            }
            word[i] = c;
        }
        return false;
    }
private:
    unordered_map<string, unordered_set<char>> dict_;



https://leetcode.com/problems/implement-magic-dictionary/discuss/107446/Easy-14-lines-Java-solution-HashMap
  1. For each word in dict, for each char, remove the char and put the rest of the word as key, a pair of index of the removed char and the char as part of value list into a map. e.g.
    "hello" -> {"ello":[[0, 'h']], "hllo":[[1, 'e']], "helo":[[2, 'l'],[3, 'l']], "hell":[[4, 'o']]}
  2. During search, generate the keys as in step 1. When we see there's pair of same index but different char in the value array, we know the answer is true. e.g.
    "healo" when remove a, key is "helo" and there is a pair [2, 'l'] which has same index but different char. Then the answer is 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;
    }


X. http://www.cnblogs.com/grandyang/p/7612918.html
    void buildDict(vector<string> dict) {
        for (string word : dict) s.insert(word);
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        for (int i = 0; i < word.size(); ++i) {
            char t = word[i];
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == t) continue;
                word[i] = c;
                if (s.count(word)) return true;
            }
            word[i] = t;
        }
        return false;
    }
    
private:
    unordered_set<string> s;

at
Labels: , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts