link
memorized DFS, DP1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27// import java.util.*;
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
return backtrack(s,wordDict,new HashMap<String, List<String>>());
}
// backtrack returns an array including all substrings derived from s.
public List<String> backtrack(String s, List<String> wordDict, Map<String,List<String>> mem){
if(mem.containsKey(s)) return mem.get(s);
List<String> result = new ArrayList<>();
for(String word: wordDict)
if(s.startsWith(word)) {
String next = s.substring(word.length());
if(next.length()==0) result.add(word);
else for(String sub: backtrack(next, wordDict, mem)) result.add(word+" "+sub);
}
mem.put(s, result);
return result;
}
}
/*
public class MyClass {
public static void main(String[] args) {
String s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
List<String> wordDict=new ArrayList<>(Arrays.asList("a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"));
System.out.println(new Solution().wordBreak(s, wordDict));
}
}*/