Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example 1:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Example 2:
Input: words = ["cat","dog","catdog"] Output: ["catdog"]
有啥是双重for循环解决不了的问题吗？没有。查找剩下的一截，算是常用模板了吧
参考：https://leetcode.com/problems/concatenated-words/discuss/541520/Java-DFS-%2B-Memoization-Clean-code
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> ans = new ArrayList<>();
HashSet<String> wordSet = new HashSet<>(Arrays.asList(words));
HashMap<String, Boolean> cache = new HashMap<>();
for (String word : words) {
System.out.println("整个的大word = " + word);
if (dfs(word, wordSet, cache))
ans.add(word);
}
return ans;
}
boolean dfs(String word, HashSet<String> wordSet, HashMap<String, Boolean> cache) {
//已经判断过了的话，就直接返回
if (cache.containsKey(word)) return cache.get(word);
for (int i = 1; i < word.length(); i++) {
//如果包括了前半截
if (wordSet.contains(word.substring(0, i))) {
//就计算后半截
String suffix = word.substring(i);
//如果后半截在set中 or dfs能找到后半截，这个word就可以拼，返回true
if (wordSet.contains(suffix) || dfs(suffix, wordSet, cache)) {
System.out.println("前半截word.substring(0, i) = " + word.substring(0, i));
System.out.println("后半截suffix = " + suffix);
System.out.println("此时这个word为true = " + word);
System.out.println(" ");
cache.put(word, true);
return true;
}
}
}
cache.put(word, false);
return false;
}
}
/*
一开始cat cats是缓存里的true，所以对整个的catsdogcats递归
整个的大word = cat
整个的大word = cats
整个的大word = catsdogcats
前半截word.substring(0, i) = dog
后半截suffix = cats
此时这个word为true = dogcats
前半截word.substring(0, i) = cats
后半截suffix = dogcats
此时这个word为true = catsdogcats
整个的大word = dog
整个的大word = dogcatsdog
前半截word.substring(0, i) = cats
后半截suffix = dog
此时这个word为true = catsdog
前半截word.substring(0, i) = dog
后半截suffix = catsdog
此时这个word为true = dogcatsdog
整个的大word = hippopotamuses
整个的大word = rat
整个的大word = ratcatdogcat
前半截word.substring(0, i) = dog
后半截suffix = cat
此时这个word为true = dogcat
前半截word.substring(0, i) = cat
后半截suffix = dogcat
此时这个word为true = catdogcat
前半截word.substring(0, i) = rat
后半截suffix = catdogcat
此时这个word为true = ratcatdogcat
*/