Java | Trie & Sort & DFS | 91ms | Some thoughts.
Sort it by length in ascending order because we only need to try to form the current string with shorter strings.\nThen we construct the trie as we go and do a 
Sort it by length in ascending order because we only need to try to form the current string with shorter strings.\nThen we construct the trie as we go and do a dfs on each word.\n\nFor the DFS, we generally have two possible options:\n- Continue with the current word\n- If the current index has a valid word ended there, start a new DFS from the root Trie.\n\nHere is the normal version that **passed** it in 91ms, but it has a fatal flaw and **should NOT have passed**.\nCould you see where the problem is?\n```Java\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<String> ans = new ArrayList<>();\n        Trie root = new Trie();\n        Arrays.sort(words, Comparator.comparingInt(o->o.length()));\n        for (String s : words){\n            if (dfs(0,s,root,root)){ // check for current word\n                ans.add(s);\n            }\n            Trie cur = root;\n            for (char ch : s.toCharArray()){ // build tree\n                if (cur.nodes[ch-\'a\']==null){\n                    cur.nodes[ch-\'a\']=new Trie();\n                }\n                cur=cur.nodes[ch-\'a\'];\n            }\n            cur.isWord=true;\n        }\n        return ans;\n    }\n\n    private boolean dfs(int idx, String s, Trie cur, Trie root){\n        if (cur==null){\n            return false;\n        }\n        if (idx==s.length()){\n            return cur.isWord;\n        }\n        return cur.isWord && dfs(idx,s,root,root)||dfs(idx+1,s,cur.nodes[s.charAt(idx)-\'a\'],root); // two options.\n    }\n\n    private class Trie {\n        Trie[] nodes = new Trie[26];\n        boolean isWord;\n        Trie(){}\n    }\n}\n```\n*Answer:*\nOne may notice that it got TLE for this test case that I discovered:\n```\n["aaaaaaaaaaaaaaaaaaaaaaaaaaab","a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa","aaaaaaaaaaa","aaaaaaaaaaaa","aaaaaaaaaaaaa","aaaaaaaaaaaaaa","aaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaa"]\n```\nHence, we need to add memo to avoid it.\n- In particular, we will not allow DFS to start **anew** at an index that was previous explored anew as well.\n- If you don\'t like to reallocate at most 30 new bytes per word, use `int[]` and a rolling `id` to mark as seen.\n- Byte? isn\'t boolean in Java bit? No, JVM usually reserves 1 byte for boolean.\n```Java\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<String> ans = new ArrayList<>();\n        Trie root = new Trie();\n        Arrays.sort(words, Comparator.comparingInt(o->o.length()));\n        for (String s : words){\n            if (dfs(0,s,root,root, new boolean[s.length()])){\n                ans.add(s);\n            }\n            Trie cur = root;\n            for (char ch : s.toCharArray()){\n                if (cur.nodes[ch-\'a\']==null){\n                    cur.nodes[ch-\'a\']=new Trie();\n                }\n                cur=cur.nodes[ch-\'a\'];\n            }\n            cur.isWord=true;\n        }\n        return ans;\n    }\n\n    private boolean dfs(int idx, String s, Trie cur, Trie root, boolean[] seen){\n        if (cur==null){\n            return false;\n        }\n        if (idx==s.length()){\n            return cur.isWord;\n        }\n        if (cur==root){ // memo\n            if (seen[idx]){\n                return false;\n            }\n            seen[idx]=true;\n        }\n        return cur.isWord && dfs(idx,s,root,root,seen)||dfs(idx+1,s,cur.nodes[s.charAt(idx)-\'a\'],root,seen);\n    }\n\n    private class Trie {\n        Trie[] nodes = new Trie[26];\n        boolean isWord;\n        Trie(){}\n    }\n}\n```
['Trie', 'Java']