@@ -0,0 +1,2768 @@
+package advanced.dp.n2.lc472_concatenatedwords;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Map;%0Aimport java.util.Set;%0A%0A/**%0A */%0Apublic class Solution %7B%0A%0A    public List%3CString%3E findAllConcatenatedWordsInADict(String%5B%5D words) %7B%0A        Set%3CString%3E dict = new HashSet%3C%3E(Arrays.asList(words));%0A        List%3CString%3E ret = new ArrayList%3C%3E();%0A        for (String w : words) %7B%0A            if (dfs(w, dict, 1)) ret.add(w);%0A        %7D%0A        return ret;%0A    %7D%0A%0A    private boolean dfs(String word, Set%3CString%3E dict, int cnt) %7B%0A        for (int i = 0; i %3C word.length(); i++) %7B // suf from entire word to one char%0A            String suf = word.substring(i);%0A            if (!dict.contains(suf)) continue;%0A            if (i == 0 && cnt %3E= 2) return true;%0A            if (dfs(word.substring(0, i), dict, cnt + 1)) return true;%0A        %7D%0A        return false;%0A    %7D%0A%0A    public List%3CString%3E findAllConcatenatedWordsInADict_DP(String%5B%5D words) %7B%0A        Map%3CString,Boolean%3E memo = new HashMap%3C%3E();%0A        Set%3CString%3E dict = new HashSet%3C%3E(Arrays.asList(words));%0A        List%3CString%3E ret = new ArrayList%3C%3E();%0A        for (String w : words) %7B%0A            if (dfs(w, memo, dict)) ret.add(w);%0A        %7D%0A        return ret;%0A    %7D%0A%0A    private boolean dfs(String word, Map%3CString,Boolean%3E memo, Set%3CString%3E dict) %7B%0A        if (memo.containsKey(word)) return memo.get(word);%0A        for (int i = 1; i %3C word.length(); i++) %7B // suf from n-1 word to one char%0A            String suf = word.substring(i);%0A            if (!dict.contains(suf)) continue;%0A%0A            String pre = word.substring(0, i);%0A            if (dict.contains(pre) %7C%7C dfs(pre, memo, dict)) %7B%0A                memo.put(word, true);%0A                return true;%0A            %7D%0A        %7D%0A        memo.put(word, false);%0A        return false;%0A    %7D%0A%0A    // O(n*len*len). Idea from Word Break I. TLE...%0A    // For %22hello void%22 and %22hello world%22, Trie could save time of prefix %22hello%22 check, but Set cannot.%0A    public List%3CString%3E findAllConcatenatedWordsInADict2(String%5B%5D words) %7B%0A        Set%3CString%3E memo = new HashSet%3C%3E();%0A        Set%3CString%3E dict = new HashSet%3C%3E(Arrays.asList(words));%0A        List%3CString%3E ret = new ArrayList%3C%3E();%0A        for (String s : words) %7B%0A            for (int i = 1; i %3C= s.length(); i++) %7B%0A                for (int j = 1; j %3C i; j++) %7B%0A                    String pre = s.substring(0, j), suf = s.substring(j, i);%0A                    if ((memo.contains(pre) %7C%7C dict.contains(pre)) && dict.contains(suf)) %7B%0A                        memo.add(s.substring(0, i));%0A                    %7D%0A                %7D%0A            %7D%0A            if (memo.contains(s)) ret.add(s);%0A        %7D%0A        return ret;%0A    %7D%0A%0A%7D%0A

concatenated words