# 472 Concatenated Words
給一String Array dictionary,回傳List
example:
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Idea 首先想到比較長的字一定是由比較短的字組成,所以把input 照字串長度sort。 再創一個Set,當讀到word[i]時,就把i之前的字都存進set。 判斷word[i]是否要存進result,就走過word[i]中所有可能的substring,判斷substring有沒有在set中。
Pseudocode
Main:
sort words by length
create a set
for each word in words
if(canForm returns true)
put word into result
put word into set
return result
canForm:
boolean[] dp -> record if the substring ends at i exist in set
dp[0]=true
for substring end at i
for substring start at j
if dp[j] is false, continue
if substring(j,i) is in set
dp[i] = true;
break
return dp[length of word]
Code
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Arrays.sort(words, new Comparator<String>(){
public int compare(String a, String b){
return a.length() - b.length();
}
});
List<String> res = new ArrayList<>();
Set<String> set = new HashSet<>();
for(int i=0; i<words.length; i++){
if(canForm(words[i], set)){
res.add(words[i]);
}
set.add(words[i]);
}
return res;
}
private boolean canForm(String word, Set<String> dict){
boolean[] dp = new boolean[word.length()+1];
dp[0] = true;
if(dict.isEmpty()) return false;
for(int i = 1; i <= word.length(); i++){
for(int j=0; j < i; j++){
if(!dp[j]) continue;
if(dict.contains(word.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[word.length()];
}
}
這個解法的efficiency不是很好,可以進而用recursive寫法來改善。 canForm的每個迴圈變成只看substring(0,i)存不存在set中,把右半邊再丟進canForm,做一樣的計算。
public class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> ret = new ArrayList<>();
Set<String> set = new HashSet<>();
for (String word : words) {
set.add(word);
}
for (String word : words) {
if (canForm(set, word)) ret.add(word);
}
return ret;
}
private boolean canForm(Set<String> set, String s) {
for (int i = 1; i < s.length(); i++) {
if (set.contains(s.substring(0, i))) {
String rightStr = s.substring(i);
if (set.contains(rightStr) || canForm(set, rightStr))
return true;
}
}
return false;
}
}