[Java] DFS + Memoization - Clean code
Solution 1: Straigtforward DFS + Memoization\njava\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<St
**Solution 1: Straigtforward DFS + Memoization**\n```java\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<String> ans = new ArrayList<>();\n        HashSet<String> wordSet = new HashSet<>(Arrays.asList(words));\n        HashMap<String, Boolean> cache = new HashMap<>();\n        for (String word : words) if (dfs(word, wordSet, cache)) ans.add(word);\n        return ans;\n    }\n    boolean dfs(String word, HashSet<String> wordSet, HashMap<String, Boolean> cache) {\n        if (cache.containsKey(word)) return cache.get(word);\n        for (int i = 1; i < word.length(); i++) {\n            if (wordSet.contains(word.substring(0, i))) {\n                String suffix = word.substring(i);\n                if (wordSet.contains(suffix) || dfs(suffix, wordSet, cache)) {\n                    cache.put(word, true);\n                    return true;\n                }\n            }\n        }\n        cache.put(word, false);\n        return false;\n    }\n}\n```\n\n**Solution 2: Concise**\n```java\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<String> ans = new ArrayList<>();\n        HashSet<String> wordSet = new HashSet<>(Arrays.asList(words));\n        for (String word : words) if (dfs(word, wordSet)) ans.add(word);\n        return ans;\n    }\n    boolean dfs(String word, HashSet<String> wordSet) {\n        for (int i = 1; i < word.length(); i++) {\n            if (wordSet.contains(word.substring(0, i))) {\n                String suffix = word.substring(i);\n                if (wordSet.contains(suffix) || dfs(suffix, wordSet)) {\n                    wordSet.add(word); // can treat concatenated word as a new word for quickly lookup later\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n}\n```\n**Solution 3: Cache nonCombination**\n```java\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<String> ans = new ArrayList<>();\n        HashSet<String> wordSet = new HashSet<>(Arrays.asList(words));\n        HashSet<String> nonCombination = new HashSet<>();\n        for (String word : words) if (dfs(word, wordSet, nonCombination)) ans.add(word);\n        return ans;\n    }\n    boolean dfs(String word, HashSet<String> wordSet, HashSet<String> nonCombination) {\n        if (nonCombination.contains(word)) return false;\n        for (int i = 1; i < word.length(); i++) {\n            if (wordSet.contains(word.substring(0, i))) {\n                String suffix = word.substring(i);\n                if (wordSet.contains(suffix) || dfs(suffix, wordSet, nonCombination)) {\n                    wordSet.add(word); // can treat concatenated word as a new word for quickly lookup later\n                    return true;\n                }\n            }\n        }\n        nonCombination.add(word);\n        return false;\n    }\n}\n```\n\n**Solution 4: Trie**\n```java\nclass Solution {\n    class TrieNode {\n        TrieNode[] children = new TrieNode[26];\n        boolean isWord;\n    }\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        TrieNode root = new TrieNode();\n        for (String word : words) {\n            TrieNode current = root;\n            for (char c : word.toCharArray()) {\n                if (current.children[c-\'a\'] == null) current.children[c-\'a\'] = new TrieNode();\n                current = current.children[c-\'a\'];\n            }\n            if (current != root) current.isWord = true;\n        }\n        List<String> ans = new ArrayList<>();\n        for (String word : words) if (dfs(root, word.toCharArray(), 0, word.length() - 1)) ans.add(word);\n        return ans;\n    }\n    boolean dfs(TrieNode root, char[] cstr, int left, int right) {\n        TrieNode current = root;\n        for (int i = left; i <= right; i++) {\n            char c = cstr[i];\n            if (current.children[c-\'a\'] == null) return false;\n            current = current.children[c-\'a\'];\n            if (current.isWord) { // prefix\n                if (isWord(root, cstr, i + 1, right) || dfs(root, cstr, i + 1, right))\n                    return true;\n            }\n        }\n        return false;\n    }\n    boolean isWord(TrieNode root, char[] cstr, int left, int right) {\n        TrieNode current = root;\n        for (int i = left; i <= right; i++) {\n            char c = cstr[i];\n            if (current.children[c-\'a\'] == null) return false;\n            current = current.children[c-\'a\'];\n        }\n        return current.isWord;\n    }\n}\n```\n\nSmilliar problems:\n- [139. Word Break](https://leetcode.com/problems/word-break/)\n- [140. Word Break II](https://leetcode.com/problems/word-break-ii/)
[]