# 472 Concatenated Words

給一String Array dictionary，回傳List 裡面存dictionary中由dictionary裡的字組成的字。

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;
    }
}