JAVA DP + Trie 75ms
Step 1: created Trie from words\nStep 2: check each word\n\tdp[i]: number of concatenated words  for substring of word[i, word.length() - 1]\n\tfor each index i
Step 1: created Trie from words\nStep 2: check each word\n\tdp[i]: number of concatenated words  for substring of word[i, word.length() - 1]\n\tfor each index i at each word, check the second part of word[i, n -1] is a word.\n\tdp[i] >= 2 means it can be concatenated from two words \n\t\nTime complexity: O(m * n^2).   Geneate Trie. O(m * n). dp check each word O(n^2). m loops\nSpace complexity: O(m * n*).   O(m*n) for Trie and O(n) for dp\n\nm: words.length\nn: maximum word length\n```\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        TrieNode root = new TrieNode();\n\t\t//put each word in the Trie\n        for(String word : words) {\n            insertWord(root, word);\n        }\n        List<String> result = new ArrayList<>();\n\t\t//check each word\n        for (String word : words) {\n            if (isConcatenated(word, root)){\n                result.add(word);\n            }\n        }\n        return result;\n    }\n    private boolean isConcatenated(String word, TrieNode root) {\n        int[] dp = new int[word.length() + 1];\n        dp[word.length()] = 0;\n        for (int i = word.length() - 1; i >= 0; i--) {\n            TrieNode cur = root;\n            dp[i] = -1;\n\t\t\t//check word substring from right to left\n            for (int j = i; j < word.length(); j++) {\n                cur = cur.children[word.charAt(j) - \'a\'];\n                if (cur == null) {\n                    break;\n                }\n\t\t\t\t//if prefix does not exist, no need to check further\n                if (cur.isWord && dp[j + 1] != -1) {\n                    dp[i] = dp[j + 1] + 1;\n                    if (dp[i] >= 2) {\n                        break;\n                    }\n\t\t\t\t\t//once found it can be composed by two words, break\n                }\n            }\n        }\n        return dp[0] >= 2;\n    }\n    private void insertWord(TrieNode root, String word) {\n        TrieNode cur = root;\n        for (char c : word.toCharArray()) {\n            TrieNode next = cur.children[c - \'a\'];\n            if (next == null) {\n                next = new TrieNode();\n                cur.children[c - \'a\'] = next;\n            }\n            cur = next;\n        }\n        cur.isWord = true;\n    }\n    private class TrieNode {\n        TrieNode[] children = new TrieNode[26];\n        boolean isWord = false;\n    }\n}\n```
[]