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;
        for(String word:words){
        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++){
                    TrieNode newChild = new TrieNode();
          [word[i]-'a'] = newChild;
                curr =[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;
        //choose to continue looking deeper in the Trie or go back and check from root again.
                return findWord(word,pos+1,[word.charAt(pos)-'a'],wordcount)||findWord(word,pos+1,root,wordcount+1);
                //***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,[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.