Simple Java Trie + DFS solution 144ms
Most of lines are adding words into Trie Tree \nThis solution is like putting two pointers to search through the tree. When find a word, put the other pointer b
Most of lines are adding words into Trie Tree \nThis solution is like putting two pointers to search through the tree. When find a word, put the other pointer back on root then continue searching.\nBut I'm not sure about the time complexity of my solution. Suppose word length is len and there are n words. Is the time complexity O(len * n ^ 2)?\n```\npublic class Solution {\n    class TrieNode {\n        TrieNode[] children;\n        String word;\n        boolean isEnd;\n        boolean combo; //if this word is a combination of simple words\n        boolean added; //if this word is already added in result\n        public TrieNode() {\n            this.children = new TrieNode[26];\n            this.word = new String();\n            this.isEnd = false;\n            this.combo = false;\n            this.added = false;\n        }\n    }\n    private void addWord(String str) {\n        TrieNode node = root;\n        for (char ch : str.toCharArray()) {\n            if (node.children[ch - 'a'] == null) {\n                node.children[ch - 'a'] = new TrieNode();\n            }\n            node = node.children[ch - 'a'];\n        }\n        node.isEnd = true;\n        node.word = str;\n    }\n    private TrieNode root;\n    private List<String> result;\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        root = new TrieNode();\n        for (String str : words) {\n            if (str.length() == 0) {\n                continue;\n            }\n            addWord(str);\n        }\n        result = new ArrayList<>();\n        dfs(root, 0);\n        return result;\n    }\n    private void dfs(TrieNode node, int multi) {\n    \t//multi counts how many single words combined in this word\n        if(node.isEnd && !node.added && multi > 1) {\n            node.combo = true;\n            node.added = true;\n            result.add(node.word);\n        }\n        searchWord(node, root, multi);\n    }\n    private void searchWord(TrieNode node1, TrieNode node2, int multi) {\n        if (node2.combo) {\n            return;\n        }\n        if (node2.isEnd) {\n            //take the pointer of node2 back to root\n            dfs(node1, multi + 1);\n        }\n        for (int  i = 0; i < 26; i++) {\n            if (node1.children[i] != null && node2.children[i] != null) {\n                searchWord(node1.children[i], node2.children[i], multi);\n            }\n        }\n    }\n}\n```
[]