472. Concatenated Words （H）

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"]

Constraints:

• 1 <= words.length <= 104

• 0 <= words[i].length <= 30

• words[i] consists of only lowercase English letters.

• 0 <= sum(words[i].length) <= 105

Solution:

Version 1: DP:

DP求解 对于words中的每个单词w，定义一个数组dpn+1，如果dpi == true，则表示w.substr(0, i)可以由words中的已有单词连接而成。 那么状态转移方程就是：dpi = || {dpj && w.substr(j + 1, i - j) is in words}，其中j < i。 最终检查dpn是否为true，如果是则将其加入结果集中。 为了加速对words中的单词的查找，用一个哈希表来保存各个单词。 这样时间复杂度可以降低到O(n * m^2)，其中n是words中的单词的个数，m是每个单词的平均长度（或者最大长度）。

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        
        List<String> result = new ArrayList<String>();
        Set<String> dict = new HashSet<String>();
        for(String word: words)
        {
            dict.add(word);
        }
        
        for(String word: words)
        {
            if(canBreak(dict, word))
            {
                result.add(word);
            }
        }
        return result; 
    }
    
    public boolean canBreak(Set<String> dict, String word)
    {
        int n = word.length();
        if (n == 0) {
            return false;
        }
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        
        for(int i = 1; i<= n; i++)
        {
            for(int j = 0; j<i; j++)
            {
                // word itself
                if(i == n && j == 0) continue;
                dp[i] = dp[j] && dict.contains(word.substring(j,i));
                
                //下面一句很重要，两个for循环嵌套。
                //因为break语句位于内层的for循环，因此，它会跳出内层for循环，但不会跳出外层for循环。
                if(dp[i]) break;
            }
        }
        return dp[n];
    }
    
    
}

Version 2 DFS:

利用HashSet记录已知单词, 以及能使用已知单词组合而成的新单词.

利用recursion检查当前单词可否用已知单词组合而成.

  public List<String> findAllConcatenatedWordsInADict(String[] words) {
        
        List<String> res = new ArrayList<>();

        Set<String> set = new HashSet<>();
        for (String w : words) {
            set.add(w);
        }

        for (String w : words) {
            if (w.length() == 0) {
                continue;
            }
            set.remove(w);
            if (cando(set, w)) {
                res.add(w);
            }
            set.add(w);
        }

        return res;
    }

    boolean cando(Set<String> set, String word) {
     
        if (word.length() == 0) {
            return true;
        }
        for (int i = 1; i <= word.length(); i++) {
            String t = word.substring(0, i);
            if (set.contains(t)) {
                if (cando(set, word.substring(i))) {
                    return true;
                }
            }
        }
        return false;
    }