Trie Tree java solution! very easy to understand!


  • 13

    This solution uses Trier tree and DFS to search '.' case.

    1, first build the standard trier tree root.
    2, add the word into the tree.
    3, basic search for normal character 'a'-'z' and DFS for the '.'
    

    Here is the solution, it is fast that beat 80%-90% solutions.

    public class WordDictionary {
    
        // Adds a word into the data structure.
        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;
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.