-
Notifications
You must be signed in to change notification settings - Fork 5
/
Day-30 Word Break II
32 lines (32 loc) · 1.01 KB
/
Day-30 Word Break II
1
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
28
29
30
31
32
class Solution {
List<String> wordDict=null;
String s=null;
public List<String> wordBreak(String s, List<String> wordDict) {
this.wordDict = wordDict;
this.s = s;
int length = s.length();
List<String>[] result = new ArrayList[length];
helper(0, length, result);
return result[0];
}
List<String> helper(int position, int length, List<String>[] result){
if(result[position] != null){
return result[position];
}
List<String> posStr = new ArrayList<>();
for(String w:wordDict){
if(s.startsWith(w,position)){
if(position + w.length() == length){
posStr.add(w);
continue;
}
List<String> temp = helper(position + w.length(), length, result);
for(String r : temp){
posStr.add(w + " " + r);
}
}
}
result[position]=posStr;
return posStr;
}
}