> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/472.-concatenated-words.md).

# 472. Concatenated Words

first thinking, no sort, and put all words into hashset

-> time limit exceeded

```java
class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> wordDict = new HashSet<>();
        for (String w : words) {
            if (w.length() != 0) {
                wordDict.add(w);
            }
        }
        // System.out.println(wordDict.size());
        List<String> result = new ArrayList<>();
        for (String w : words) {
            if (w.length() != 0 && wordBreak(w, wordDict)) {
                result.add(w);
            }
        }
        return result;
    }
    
    public boolean wordBreak(String s, Set<String> wordDict) {
        return dfs(s, 0, wordDict, new Boolean[s.length()]);
    }
    private boolean dfs(String s, int start, Set<String> wordDict, Boolean[] memo) {
        if (start == s.length()) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (String w : wordDict) {
            if (s.equals(w)) {
                continue;
            }
            int len = w.length();
            if (start + len > s.length()) { // can be s.length() -> in next call, go to base condition
                continue;
            }
            String sub = s.substring(start, start + len);
            if (w.equals(sub)) {
                if (dfs(s, start + len, wordDict, memo)) {
                    return memo[start] = true;
                }
            }
        }
        return memo[start] = false;
    }
}

/*

1. use word break thinking
"catsdogcats"

from words , 

if word same to s, skip

if it's true -> add to output

(needs exclude empty string edge case)

*/
```

do sort, shorter one is in front

```
...in this way, don't need to filter same word(because it doesn't add to dict)
also don't care about "", because it's only add to dict, but not add to output!

```

```java
class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length()); // smaller word put previous, 
        
        List<String> result = new ArrayList<>();
        Set<String> wordDict = new HashSet<>(); // 
        for (String w : words) {
            if (wordDict.size() > 0 && dfs(w, 0, wordDict, new Boolean[w.length()])) {
                result.add(w);
            }
            wordDict.add(w);
        }
        return result;
    }
    private boolean dfs(String s, int start, Set<String> wordDict, Boolean memo[]) {
        if (s.length() == start) {
            return true;
        }
        if (memo[start] != null) {
            return memo[start];
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (wordDict.contains(s.substring(start, end)) && dfs(s, end, wordDict, memo)) {
                return memo[start] = true;
            }
        }
        return memo[start] =false;
    }
}

/*
smaller word put previous
["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
->

["cat","dog","rat", "cats","dogcatsdog","catsdogcats","ratcatdogcat","hippopotamuses"]

is concatenated word?
then
we can add to dict one by one

ex:
"cat" -> no
dict["cat"]
"dog" -> no
dict["cat", "dog"]
"rat" -> no
dict["cat", "dog", "rat"]

"cats" -> no
dict["cat", "dog", "rat", "cats"]

"dogcatsdog" -> yes! -> add to output
dict["cat", "dog", "rat", "cats", "dogcatsdog"]

"catsdogcats" -> yes! -> add to output
dict["cat", "dog", "rat", "cats", "dogcatsdog", "catsdogcats"]

...in this way, don't need to filter same word(because it doesn't add to dict)
also don't care about "", because it's only add to dict, but not add to output!
*/
```