Java DP Solution
Do you still remember how did you solve this problem? https://leetcode.com/problems/word-break/\n\nIf you do know one optimized solution for above question is u
Do you still remember how did you solve this problem? https://leetcode.com/problems/word-break/\n\nIf you do know one optimized solution for above question is using ```DP```, this problem is just one more step further. We iterate through each ```word``` and see if it can be formed by using other ```words```.\n\nOf course it is also obvious that a ```word``` can only be formed by ```words``` shorter than it. So we can first sort the input by length of each ```word```, and only try to form one ```word``` by using ```words``` in front of it.\n```\npublic class Solution {\n    public static List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<String> result = new ArrayList<>();\n        Set<String> preWords = new HashSet<>();\n        Arrays.sort(words, new Comparator<String>() {\n            public int compare (String s1, String s2) {\n                return s1.length() - s2.length();\n            }\n        });\n        \n        for (int i = 0; i < words.length; i++) {\n            if (canForm(words[i], preWords)) {\n                result.add(words[i]);\n            }\n            preWords.add(words[i]);\n        }\n        \n        return result;\n    }\n\t\n    private static boolean canForm(String word, Set<String> dict) {\n        if (dict.isEmpty()) return false;\n\tboolean[] dp = new boolean[word.length() + 1];\n\tdp[0] = true;\n\tfor (int i = 1; i <= word.length(); i++) {\n\t    for (int j = 0; j < i; j++) {\n\t\tif (!dp[j]) continue;\n\t\tif (dict.contains(word.substring(j, i))) {\n\t\t    dp[i] = true;\n\t\t    break;\n\t\t}\n\t    }\n\t}\n\treturn dp[word.length()];\n    }\n}\n```
[]