472. Concatenated Words

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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 <= 1000
words[i] consists of only lowercase English letters.
0 <= sum(words[i].length) <= 105

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<>();
        Set<String> set = new HashSet<>(Arrays.asList(words));
        for (String word: words) {
            if (word.length() == 0) continue;
            set.remove(word);
            boolean[] dp = new boolean[word.length() + 1];
            dp[0] = true;
            for (int i = 1; i < dp.length; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (dp[j] && set.contains(word.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            if (dp[word.length()]) {
                res.add(word);
            }
            set.add(word);
        }
        return res;
    }    
    
    public List<String> findAllConcatenatedWordsInADict2(String[] words) {
        List<String> res = new ArrayList<>();
        List<String> current = new ArrayList<>();
        Arrays.sort(words, (w1, w2) -> Integer.compare(w1.length(), w2.length()));
        Set<String> set = new HashSet<>(Arrays.asList(words));
        for (String word: words) {
            set.remove(word);
            if (dfs(word, set, "")) {
                res.add(word);
            }
            set.add(word);
        }
        return res;
    }
    boolean dfs(String word, Set<String> set, String prev) {
        if (set.contains(word)) return true;
        for (int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0, i);
            if (set.contains(prefix)) {
               String newPrefix = prev + prefix; 
               set.add(newPrefix); 
               if (dfs(word.substring(prefix.length(), word.length()), set, newPrefix)) {
                   return true;
               }
            }
        }
        return false;
    }
}

Solution#

Solution