472. Concatenated Words

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

-> time limit exceeded

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!

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!
*/