Extremely Short Java Trie Solution 120ms.


  • 0

    I feel the top voted Trie solution is too complicated while much of it is unnecessary.

    public class Solution {
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> res = new LinkedList<>(); 
            Trie root = new Trie();
            for(String s: words){//build tree
                 Trie p = root;
                 for(char c: s.toCharArray()){
                     if(p.next[c-'a']==null) p.next[c-'a'] = new Trie();  
                     p = p.next[c-'a']; 
                 }
                 p.word = s; 
            }
            for(String s: words) 
                if(dfs(s, root, 0, root)) res.add(s); //check each word using the tree
            return res;
        }
        private boolean dfs(String s, Trie t, int p, Trie root){
            //return true, if we reach a word at the end & the original word s is a concatenated word
            if(p==s.length()) return t.word!=null && !t.word.equals(s); 
            if(t.next[s.charAt(p)-'a']==null) return false; 
            //reached a word, try to start from root again
            if(t.next[s.charAt(p)-'a'].word!=null && dfs(s, root, p+1, root)) return true; 
            //keep going
            return dfs(s, t.next[s.charAt(p)-'a'] ,p+1, root); 
        }
        class Trie{
            Trie[] next = new Trie[26];
            String word = null; 
        }
    }
    

Log in to reply
 

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