Java || DFS || Similar to Word Break
\n\t// O(log(words.lengthlog(words.length)) + O(words.lengthwords[i].length^2))\n\tpublic List findAllConcatenatedWordsInADict(String[] words) {\n\n\t\tList res
\n\t// O(log(words.length*log(words.length)) + O(words.length*words[i].length^2))\n\tpublic List<String> findAllConcatenatedWordsInADict(String[] words) {\n\n\t\tList<String> res = new ArrayList<String>();\n\t\tif (words.length == 1)\n\t\t\treturn res;\n\n\t\tArrays.sort(words, new Comparator<String>() {\n\t\t\t@Override\n\t\t\tpublic int compare(String o1, String o2) {\n\t\t\t\treturn o1.length() - o2.length();\n\t\t\t}\n\t\t});\n\n\t\tHashSet<String> dict = new HashSet<String>();\n\t\tfor (String word : words) {\n\t\t\tif (word.length() != 0 && wordBreak(word, dict))\n\t\t\t\tres.add(word);\n\t\t\tdict.add(word);\n\t\t}\n\n\t\treturn res;\n\t}\n\n\t// O(s.length^2)\n\tpublic boolean wordBreak(String s, HashSet<String> dict) {\n\t\tint[] memo = new int[s.length()];\n\t\tint len = s.length();\n\t\treturn wordBreakDFS(len - 1, s, dict, memo);\n\t}\n\n\t// O(s.length^2)\n\tpublic boolean wordBreakDFS(int start, String s, HashSet<String> dict, int[] memo) {\n\n\t\tif (start == -1)\n\t\t\treturn true;\n\n\t\tif (memo[start] == 1)\n\t\t\treturn false;\n\n\t\tboolean ans = false;\n\t\tfor (int i = start; i >= 0; i--) {\n\t\t\tif (dict.contains(s.substring(i, start + 1))) {\n\t\t\t\tans = wordBreakDFS(i - 1, s, dict, memo);\n\t\t\t\tif (ans)\n\t\t\t\t\treturn true;\n\t\t\t}\n\t\t}\n\t\tmemo[start] = 1;\n\t\treturn false;\n\t}\n\n
[]