JAVA Trie+DFS solution


  • 1
    public class WordDictionary {
    private class Trie{
        boolean isEnd=false;
        Trie[] next;
        Trie()
        {
            next=new Trie[26];
        }
    }
    Trie[] wd=new Trie[26];
    // Adds a word into the data structure.
    public void addWord(String word) {
        Trie[] c=wd;
        for(int i=0;i<word.length();i++)
        {
            char cur=word.charAt(i);
            if(c[cur-'a']==null)
            {
                c[cur-'a']=new Trie();
            }
            if(i==word.length()-1) c[cur-'a'].isEnd=true;
            c=c[cur-'a'].next;
        }
    }
    // 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 dfs(word,0,wd,new Trie());
    }
    public boolean dfs(String word,int index, Trie[] dic,Trie pre)
    {   if(index==word.length()&&pre.isEnd==true) return true;
        if(index==word.length()&&pre.isEnd==false) return false;
        char cur=word.charAt(index);
        if(cur=='.')
        {
            for(int i=0;i<26;i++)
            {
                if(dic[i]!=null) if(dfs(word,index+1,dic[i].next,dic[i])==true) return true;
            }
        }
        else
        {
            if(dic[cur-'a']!=null) if(dfs(word,index+1,dic[cur-'a'].next,dic[cur-'a'])==true) return true; 
        }
        return false;
    }
    

    }


Log in to reply
 

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