Trie Tree Java Solution


  • 0
    T
    class TrieNode {
        TrieNode[] sons;
        boolean isEnd;
        public TrieNode() {
            sons = new TrieNode[26];
        }
    }
    
    public class WordDictionary {
        private TrieNode root;
    
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.sons[c - 'a'] == null) {
                    node.sons[c - 'a'] = new TrieNode();
                }
                node = node.sons[c - 'a'];
            }
            node.isEnd = 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) {
            TrieNode node = root;
            return backtracking(word.toCharArray(), 0, node);
        }
        
        private boolean backtracking(char[] word, int pos, TrieNode node) {
            if (pos == word.length) {
                return node.isEnd;
            }
            char c = word[pos];
            if (c == '.') {
                for (int k = 0; k < node.sons.length; k++) {
                    TrieNode son = node.sons[k];
                    if (son != null) {
                        if (backtracking(word, pos + 1, son)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                if (node.sons[c - 'a'] != null) {
                    return backtracking(word, pos + 1, node.sons[c - 'a']);
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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