BB3.java

importjava.util.*;

publicclassBB3 {
publicList<String> breakWords(Strings, Set<String> wordDict) {
returnbreakWordsHelper(s, wordDict, newHashMap<String, List<String>>());
 }

privateList<String> breakWordsHelper(Strings, Set<String> wordDict, Map<String, List<String>> memo) {
if (memo.containsKey(s)) {
returnmemo.get(s);
 }

List<String> result = newArrayList<>();

for (Stringword : wordDict) {
if (s.startsWith(word)) {
List<String> subList = breakWordsHelper(s.substring(word.length()), wordDict, memo);
for (StringsubListWord : subList) {
result.add(subListWord);
 }

result.add(word);
 }
 }

memo.put(s, result);
returnresult;
 }

publicstaticvoidmain(String[] args) {
BB3wordBreak = newBB3();

String[] words = { "cat", "cats", "and", "sand", "dog", "apple", "pen", "applepen", "pine", "pineapple", "cats",
"dog", "sand", "and", "cat", "wash", "rag" };
Set<String> wordDict = newHashSet<>(Arrays.asList(words));

StringtoBreak1 = "catsanddog";
StringtoBreak2 = "pineapplepenapple";
StringtoBreak3 = "helloworld";

List<String> splitWords1 = wordBreak.breakWords(toBreak1, wordDict);
for (Stringw : splitWords1) {
System.out.print(w + " ");
 }

System.out.println();

List<String> splitWords2 = wordBreak.breakWords(toBreak2, wordDict);
for (Stringw : splitWords2) {
System.out.print(w + " ");
 }

System.out.println();

List<String> splitWords3 = wordBreak.breakWords(toBreak3, wordDict);
for (Stringw : splitWords3) {
System.out.print(w + " ");
 }

return;
 }
}