java 41ms trie and dfs solution which beats 97%
We can solve the problem in two steps:\n1. put the given words in a trie;\n2. For each word, dfs the trie (traverse characters in the word one by one). If the t
We can solve the problem in two steps:\n1. put the given words in a trie;\n2. For each word, dfs the trie (traverse characters in the word one by one). If the trie node of current character represent a word, then for next character, we search from the root node of trie. \n\n```\npublic List<String> findAllConcatenatedWordsInADict(String[] words) {\n    Trie root = new Trie();\n    for(int i = 0; i < words.length; i++) {\n        if( words[i].length() > 0 )\n            buildTrie(root, words[i]);\n    }\n\n    List<String> resultList = new ArrayList<String>();\n    for(int i = 0; i < words.length; i++)\n        if( search(root, words[i], 0, 0) )\n            resultList.add(words[i]);\n    return resultList;\n}\n\npublic void buildTrie(Trie root, String word) {\n    Trie current = root;\n    for(int i = 0; i < word.length(); i++) {\n        int index = word.charAt(i) - \'a\';\n        if( current.array[index] == null )\n            current.array[index] = new Trie();\n        current = current.array[index];\n    }\n    current.isWord = true;\n}\n\n// num represent the number of words that current word can be comprised of\npublic boolean search(Trie root, String word, int begin, int num) {\n    Trie current = root;\n    for(int i = begin; i < word.length(); i++) {\n        int index = word.charAt(i) - \'a\';\n        if( current.array[index] == null )\n            return false;\n        current = current.array[index];\n        if( current.isWord && search(root, word, i + 1, num + 1) ) \n            return true;\n    }\n    return num >= 1 && current.isWord;\n}\n\nclass Trie {\n    Trie array[] = new Trie[26];\n    boolean isWord = false;\n}\n```
['Depth-First Search', 'Trie', 'Java']