Leetcode 211 - Add and Search Word

Leetcode211-Add and Search Word – Hu Haoyu's Blog – Learn and live

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

wordaddWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

http://shibaili.blogspot.com/2015/06/day-108-add-and-search-word-data.html
https://discuss.leetcode.com/topic/14030/my-simple-and-clean-java-code

http://yuanhsh.iteye.com/blog/2213669
The for loop in search is unnecessary and confusing.

1.     public static class TrieNode {  
2.         TrieNode[] children;  
3.         boolean isLeaf;  
4.         public TrieNode() {  
5.             children = new TrieNode[26];  
6.         }  
7.     }  
8.       
9.     private TrieNode root = new TrieNode();  
10.       
11.     // Adds a word into the data structure.  
12.     public void addWord(String word) {  
13.         if(word == null || word.isEmpty()) return;  
14.         TrieNode node = root;  
15.         for(int i=0; i<word.length(); i++) {  
16.             int j = word.charAt(i)-'a';  
17.             if(node.children[j] == null) {  
18.                 node.children[j] = new TrieNode();  
19.             }  
20.             node = node.children[j];  
21.         }  
22.         node.isLeaf = true;  
23.     }  
24.   
25.     // Returns if the word is in the data structure. A word could  
26.     // contain the dot character '.' to represent any one letter.  
27.     public boolean search(String word) {  
28.         return search(root, word, 0);  
29.     }  
30.       
31.     private boolean search(TrieNode node, String word, int start) {  
32.         if(node == null) return false;  
33.         if(start == word.length()) return node.isLeaf;  
34.         for(int i=start; i<word.length(); i++) {  
35.             char c = word.charAt(i);  
36.             if(c == '.') {  
37.                 for(int j=0; j<26; j++) {  
38.                     if(search(node.children[j], word, i+1)) return true;  
39.                 }  
40.                 return false;  
41.             } else {  
42.                 // node = node.children[c-'a'];  
43.                 // if(node == null) return false;  
44.                 return search(node.children[c-'a'], word, i+1);  
45.             }  // no need the for loop
46.         }  
47.         return false;//node.isLeaf;  
48.     } 

https://discuss.leetcode.com/topic/30548/java-19ms-solution-modified-trie-solution

1、use HashMap to categorized words by length.

  Map<Integer,TrieNode>trieMap = new HashMap<Integer,TrieNode>();

2、all words of the same length are put in to a trie.

In a normal trie solution,we can only search one letter per time,

however,there are many cases where letters are continuously the same, say "caaaab"

so we can condense these continuously duplicated letters into one trie node instead of multiple trie node

I was able to beat 100% percent of java submission( about 15ms) just using a small trick

Change the type of trieMap to an array

TrieNode[]trieMap = new TrieNode[512];  //the maximum length of all testd words is about 500

X. Trie + DFS

    Trier root = new Trier();
    public void addWord(String word) {
        Trier pointer = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (pointer.children[c-'a'] == null) {
                pointer.children[c-'a'] = new Trier();
                pointer = pointer.children[c-'a'];
            } else {
                pointer = pointer.children[c-'a'];
            }
        }
        pointer.flag = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        Trier pointer = root;
        return helper(word,0,pointer);
    }
    private boolean helper(String word, int start, Trier cur) {
        if (start == word.length()) {
            if (cur.flag) {
                return true;
            } else {
                return false;
            }
        }
        char c = word.charAt(start);
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (cur.children[i] != null) {
                    if (helper(word,start+1,cur.children[i])) {
                        return true;
                    }
                }
            }
        } else {
            if (cur.children[c-'a'] == null) {
                return false;
            } else {
                return helper(word,start+1,cur.children[c-'a']);
            }
        }
        return false;
    }
    class Trier {
        Trier[] children;
        char c;
        boolean flag;
        public Trier() {
            children = new Trier[26];
            flag = false;
        }
    }

    bool dfs_search(string word, int i, TrieNode *curr) {
        if (!curr) return false;
        if (word.size() == i) { return curr->isTail; }

        if (word[i] != '.') {
            return dfs_search(word, i + 1, curr->letters[find(word[i])]);
        } else {
            for (int k = 0; k != 26; ++k) {
                if (curr->letters[k] && dfs_search(word, i + 1, curr->letters[k])) {
                    return true;
                }
            }
        }
        return false;
    }

X. Using Regulare Express:
https://discuss.leetcode.com/topic/14005/using-regular-expressions-ac-315-ms

import re
class WordDictionary:
    def __init__(self):
        self.words = '#'
    def addWord(self, word):
        self.words += word + '#'
    def search(self, word):
        return bool(re.search('#' + word + '#', self.words))

X. Not efficient  － Map<Integer, List<String>>
https://discuss.leetcode.com/topic/18171/java-solution-easy-understand
https://discuss.leetcode.com/topic/19588/java-solution-not-using-trie

    Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
    // Adds a word into the data structure.
    public void addWord(String word) {
        int index = word.length();
        if(!map.containsKey(index)){
            List<String> list = new ArrayList<String>();
            list.add(word);
            map.put(index, list);
        }else{
            map.get(index).add(word);
        }      
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        int index = word.length();
        if(!map.containsKey(index)){
            return false;
        }
        List<String> list = map.get(index);
        if(isWords(word)){
            return list.contains(word);
        }
        for(String s : list){
            if(isSame(s, word)){
                return true;
            }
        }
        return false;
    }
    
    boolean isWords(String s){
        for(int i = 0; i < s.length(); i++){
            if(!Character.isLetter(s.charAt(i))){
                return false;
            }
        }
        return true;
    }
    
    boolean isSame(String a, String search){
        if(a.length() != search.length()){
            return false;
        }
        for(int i = 0; i < a.length(); i++){
            if(search.charAt(i) != '.' && search.charAt(i) != a.charAt(i)){
                return false;
            }
        }
        return true;
    }

Read full article from Leetcode211-Add and Search Word – Hu Haoyu's Blog – Learn and live