Trie + DFS 136ms


  • 0
    1. Since we can only build words with shorter words, we first sort the words in ascending order of length
    2. traverse through the word array, for each word, use another helper function to check if this word can be construct from previous words.
    3. Use Trie to store all the previous words and search for all the prefixes of this word.
    4. A optimization is when we are doing DFS to check if the word can be construct from previous words, we always use the longest previous word first. This is really helpful for cases like ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa","aaaaaaaaaaaaaa","aaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".......]
    public class Solution {
        class TrieNode{
            TrieNode[] child;
            boolean isLeaf;
            TrieNode(){
                child=new TrieNode[26];
            }
        }
        
        class Trie{
            TrieNode root;
            Trie(){
                root=new TrieNode();
            }
            
            public void addWord(String word){
                TrieNode ptr=root;
                for(char x:word.toCharArray()){
                    if(ptr.child[x-'a']==null) ptr.child[x-'a']=new TrieNode();
                    ptr=ptr.child[x-'a'];
                }
                ptr.isLeaf=true;
            }
            
            public List<Integer> search(String word){
                List<Integer> res=new LinkedList<Integer>();
                int len=0;
                TrieNode ptr=root;
                for(char x:word.toCharArray()){
                    if(ptr.child[x-'a']==null) return res;
                    ptr=ptr.child[x-'a'];
                    len++;
                    if(ptr.isLeaf) res.add(len);
                }
                return res;
            }
        }
        
        public List<String> findAllConcatenatedWordsInADict(String[] words) {
            List<String> res=new LinkedList<>();
            if(words==null || words.length<2) return res;
            Trie trie=new Trie();
            int len=words.length;
            Arrays.sort(words, new Comparator<String>(){
                public int compare(String a, String b){
                    return a.length()-b.length();
                }
            });
            for(int i=0;i<len;i++){
                if(check(trie,words[i])) res.add(words[i]);
                trie.addWord(words[i]);
            }
            return res;
        }
        
        public boolean check(Trie trie, String word){
            if(word.length()==0) return true;
            List<Integer> list=trie.search(word);
            if(list.size()==0) return false;
            for(int len : list){
                if(check(trie, word.substring(len))) return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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