23ms dfs java solution


  • 0
    C
    class TrieNode{
        boolean isWord;
        TrieNode[] children;
        public TrieNode(){
            children = new TrieNode[26];
            isWord = false;
        }
    }
    public class WordDictionary {
        TrieNode root;
        public WordDictionary(){
            root = new TrieNode();
        }
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode p=root;
            for(int i=0; i<word.length(); i++){
                char c = word.charAt(i);
                if(p.children[c -'a']==null){
                    p.children[c -'a']=new TrieNode();
                }
                p = p.children[c -'a'];
            }
            p.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 p=root;
            return dfs(word, 0, p);
        }
        public boolean dfs(String word, int i, TrieNode p){
            if(i>=word.length()) {
                if(p.isWord) return true;
                else return false;
            }
            char c = word.charAt(i);
            if(c=='.'){
                for(int k=0; k<26; k++){
                    if(p.children[k]!=null && dfs(word, i+1, p.children[k])) return true;
                }
                return false;
            }else{
                if(p.children[c-'a']==null) return false;
                return dfs(word, i+1, p.children[c-'a']);
            }
        }
    }
    

Log in to reply
 

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