My neat java Trie + backtracking code


  • 0
    M

    Basically if I see a "." I goto backtracking solution else I just do away with normal Trie search.

    public class WordDictionary {
        
        private TrieNode root;
        
        public class TrieNode{
            boolean isWord;
            TrieNode[] next = new TrieNode[26];
        }
        public WordDictionary(){
            root = new TrieNode();
        }
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode curr = root;
            for(int i =0; i<word.length();i++){
                if (curr.next[word.charAt(i) - 'a'] == null){ 
                    TrieNode temp = new TrieNode();
                    curr.next[word.charAt(i) - 'a'] = temp;
                    curr = temp;
                }
                else{
                    curr = curr.next[word.charAt(i) - 'a'];
                }
            }
            curr.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) {
            TrieNode curr = root;
            for (int i=0;i<word.length();i++){
                if (word.charAt(i) == '.'){
                    return doRecursiveSearch(curr, i, word);
                }
                if (curr.next[word.charAt(i)-'a'] == null) return false;
                curr = curr.next[word.charAt(i)-'a'];
            }
            return curr.isWord;
        }
        
        public boolean doRecursiveSearch(TrieNode curr, int start, String word){
            if(start>=word.length()) return curr.isWord;
            
            if(word.charAt(start) == '.'){
                for (int i =0; i<26;i++){
                    if(curr.next[i]!=null && doRecursiveSearch(curr.next[i], start+1, word)) return true;
                }
            }
            else if(curr.next[word.charAt(start)-'a'] != null){
                return doRecursiveSearch(curr.next[word.charAt(start)-'a'], start+1, word);
            }
            return false;
        }
    }
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");

Log in to reply
 

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