[java/21ms] Trie DFS


  • 0
    class Trie {
        Trie[] children = new Trie[26];
        boolean isWord;
    }
    
    public class WordDictionary {
        private Trie root = new Trie();
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            Trie root = this.root;
            for (char c : word.toCharArray()) {
                if (root.children[c - 'a'] == null) {
                    root.children[c - 'a'] = new Trie();
                }
                root = root.children[c - 'a'];
            }
            root.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 search(word.toCharArray(), this.root, 0);
        }
    
        private boolean search(char[] word, Trie root, int idx) {
            // after loop, the trie node should contain value word[i]
            for (int i = idx; i < word.length; i++) {
                char c = word[i];
                if (c != '.') {
                    if (root.children[ c - 'a'] == null) {
                        return false;
                    }
                    root = root.children[c - 'a'];
                } else {
                    for (Trie next : root.children) {
                        // loop invariant
                        if (next != null && search(word, next, i + 1))
                            return true;
                    }
                    return false;
                }
            }
            return root.isWord;
        }
    }
    

Log in to reply
 

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