Clean Java Solution With Trie + DP
Intuition\nBuild the Trie with the Input words, then recursively check whether each word can be broken down such that all partitions are present in the Trie\n\n
# Intuition\nBuild the Trie with the Input words, then recursively check whether each word can be broken down such that all partitions are present in the Trie\n\n# Approach\nI did not come up with this, original solution is by @gracemeng\n\n\n# Code\n```\nclass Solution {\n    class Trie {\n        Map<Character, Trie> children;\n        String word;\n        Trie() {\n            this.children = new HashMap<>();\n            this.word = null;\n        }\n        void add(String s) {\n            Trie node = this;\n            for(char c : s.toCharArray()) {\n                node = node.children.computeIfAbsent(c, k->new Trie());\n            }\n            node.word = s;\n        }\n    }\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        Trie root = new Trie();\n        for(String word : words) {\n            root.add(word);\n        }\n        List<String> result = new ArrayList<>();\n\n        for(String word : words) {\n            Boolean[] dp = new Boolean[word.length()];\n            boolean count = isWordConcatenated(root, word, 0, 0, dp);\n            if(count) {\n                result.add(word);\n            }\n        }\n        \n        return result;\n        \n    }\n    \n    boolean isWordConcatenated(Trie root, String word, int idx, int wordsSoFar, Boolean[] dp) {\n        if(idx == word.length())\n            return wordsSoFar > 1;\n        \n        if(dp[idx] == null) {\n            Trie node = root;\n            for(int i = idx; i < word.length(); i++) {\n                if(!node.children.containsKey(word.charAt(i))) {\n                    dp[idx] = false;\n                    break;\n                }\n                node = node.children.get(word.charAt(i));\n                if(node.word != null) {\n                    boolean found = isWordConcatenated(root, word, i + 1, wordsSoFar+1, dp);\n                    if(found) {\n                        dp[idx] = true;\n                        break;\n                    }\n                }\n            }\n            dp[idx] = dp[idx] == null ? false : dp[idx];\n        }\n        return dp[idx];\n    }\n}\n```
['Java']