java Trie


  • 0
    J
        class Trie {
            Trie[] children = new Trie[26];
            boolean isWord;
        }
        
        private Trie root;
    
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new Trie();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            if (word.isEmpty()) return;
            Trie[] children = root.children;
            Trie last = null;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (children[c - 'a'] == null) children[c - 'a'] = new Trie();
                last = children[c - 'a'];
                children = last.children;
            }
            last.isWord = 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) {
            return !word.isEmpty() && search(word, 0, root);
        }
        
        private boolean search(String word, int start, Trie trie) {
            if (start > word.length() || trie == null) return false;
            if (start == word.length()) return trie.isWord;
            char c = word.charAt(start);
            Trie[] children = trie.children;
            if (c == '.') {
                for (int i = 0; i < 26; i++) {
                    if (search(word, start + 1, children[i])) return true;
                }
                return false;
            } else return search(word, start + 1, children[c - 'a']);
        }
    }
    

Log in to reply
 

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