Java simple 150ms Trie+DFS Solution with some comments


  • 1
    class TrieNode{
        public String word = null;
        public TrieNode[] next = null;
        public TrieNode(){
            next = new TrieNode[26];
        }
    }
    private TrieNode root;
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> ret = new ArrayList<>();
        if(words.length == 0) return ret;
        buildTrie(words);
        for(String word:words){
            if(findWord(word,0,root,0)){
                ret.add(word);
            }
        }
        return ret;
    }
    
    private void buildTrie(String[] words){
        root = new TrieNode();
        for(String s_word:words){
            char[] word = s_word.toCharArray();
            TrieNode curr = root;
            for(int i = 0;i<word.length;i++){
                if(curr.next[word[i]-'a']==null){
                    TrieNode newChild = new TrieNode();
                    curr.next[word[i]-'a'] = newChild;
                }
                curr = curr.next[word[i]-'a'];
            }
            curr.word = s_word;
        }
    }
    private boolean findWord(String word,int pos,TrieNode curr,int wordcount){//dfs
        if(pos==word.length()) {
            if(wordcount>1) return true;
            else return false;
        }
        if(curr.next[word.charAt(pos)-'a']!=null){
            if(curr.next[word.charAt(pos)-'a'].word!=null){
        //choose to continue looking deeper in the Trie or go back and check from root again.
                return findWord(word,pos+1,curr.next[word.charAt(pos)-'a'],wordcount)||findWord(word,pos+1,root,wordcount+1);
            }
            else{
                //***if current character is the last character of the word, but there is no corresponding node with word in trie, return false.*** 
                //ps: It cost me 30 min to figure out that I forgot this line...
                if(pos==word.length()-1) return false;
                return findWord(word,pos+1,curr.next[word.charAt(pos)-'a'],wordcount);
            }
        }
        return false;
    }

Log in to reply
 

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