原题链接在这里：https://leetcode.com/problems/concatenated-words/
题目：
Given a list of words (without duplicates), please write a program that returns all 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:
Input: ["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".
Note:
10,000600,000.题解：
For each word, it could be composed by shorter words.
Sort the words with length, then for each word check if it could be composed by previous words.
Time Complexity: O(m*logm + m*n^2). m = words.length. n = longest word length.
Space: O(m).
AC Java:
1 class Solution { 2 public List<String> findAllConcatenatedWordsInADict(String[] words) { 3 List<String> res = new ArrayList<>(); 4 if(words == null || words.length == 0){ 5 return res; 6 } 7 8 Arrays.sort(words, (a, b) -> a.length() - b.length()); 9 HashSet<String> hs = new HashSet<>(); 10 11 for(int i = 1; i < words.length; i++){ 12 hs.add(words[i - 1]); 13 if(couldCompose(words[i], hs)){ 14 res.add(words[i]); 15 } 16 } 17 18 return res; 19 } 20 21 private boolean couldCompose(String s, Set<String> hs){ 22 if(s == null || s.length() == 0 || hs == null || hs.size() == 0){ 23 return false; 24 } 25 26 int n = s.length(); 27 boolean [] dp = new boolean[n + 1]; 28 dp[0] = true; 29 for(int i = 1; i <= n; i++){ 30 for(int j = 0; j < i; j++){ 31 if(dp[j] && hs.contains(s.substring(j, i))){ 32 dp[i] = true; 33 break; 34 } 35 } 36 } 37 38 return dp[n]; 39 } 40 41 }
类似Word Break.
LeetCode 472. Concatenated Words
原文：https://www.cnblogs.com/Dylan-Java-NYC/p/12185505.html