Java with Trie


  • 0
    W
    public class WordDictionary {
        class Trie{
            int count;//useless
            Trie[] next;//point next Trie
            boolean word;//this character is the end of a word 
            
            public Trie(){
                count = 0;
                next = new Trie[26];
                word = false;
            }
        }
        
        Trie root;
    
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new Trie();
        }
        void addWord(String word,Trie root,int i){
            int x = word.charAt(i)-'a';
            if(root.next[x]==null){
                Trie xa = new Trie();
                xa.count+=1;
                root.next[x] = xa;
            }else{
                ++root.next[x].count;
            }
            if(i==word.length()-1){
                root.next[x].word = true;
                return;
            }
            addWord(word,root.next[x],i+1);
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            addWord(word,root,0);
        }
        
        boolean search(String word,Trie root,int i){
            if(root==null)return false;
            boolean res = false;
            char c = word.charAt(i);
            if(c=='.'){//bsf search
                if(i==word.length()-1){
                    for(int j=0;j<26;j++){
                        if(root.next[j]!=null&&root.next[j].word)return true;
                    }
                    return false;
                }
                for(int j=0;j<26;j++){
                    res|=search(word,root.next[j],i+1);
                }
            }else if(root.next[c-'a']!=null){
                if(i==word.length()-1){
                   if(root.next[c-'a'].word)return true;
                }else res|=search(word,root.next[c-'a'],i+1);
            }
            return res;
        }
        
        /** 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,root,0);
        }
    }
    
    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * boolean param_2 = obj.search(word);
     */
    

Log in to reply
 

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