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:
- The number of elements of the given array will not exceed 10,000
- The length sum of elements in the given array will not exceed 600,000.
- All the input string will only include lower case letters.
- The returned elements order does not matter.
一刷
題解: 從list中找出所有字符串，該字符串至少由list中的兩個(gè)單詞構(gòu)成由蘑。
我們首先按字符串長(zhǎng)度由小到大排列words. 然后構(gòu)造一個(gè)set, 依次加入set中。對(duì)于具體的字符串word拾积，如果word可以由至少set中的兩個(gè)word構(gòu)成拓巧，則該word加入結(jié)果集中。這種字符串的prefix問題傻唾，很明顯要用dynamic programming來解贤斜。
public class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> res = new ArrayList<>();
Set<String> preWords = new HashSet<>();
if(words == null || words.length == 0) return res;
Arrays.sort(words, new Comparator<String>(){
public int compare(String a, String b){
return a.length() - b.length();
}
});
for(String word : words){
if(canForm(word, preWords)) res.add(word);
preWords.add(word);
}
return res;
}
private boolean canForm(String word, Set<String> dict){
if(dict.isEmpty()) return false;
boolean[] dp = new boolean[word.length()+1];
dp[0] = true;
for(int i=1; i<=word.length(); i++){
for(int j=i-1; j>=0; j--){
if(!dp[j]) continue;
if(dict.contains(word.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[word.length()];
}
}
