/
Solution.java
executable file
·97 lines (79 loc) · 2.77 KB
/
Solution.java
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
public class Solution {
public void back(List<String> res, String path, int start,
Map<Integer, List<Integer>> backtrackmap, String s){
if(start == 0){
res.add(path);
return;
}
List<Integer> l = backtrackmap.get(start);
if(l == null) return;
for(int i = 0; i < l.size(); i++){
String newpath;
if(start == s.length())
newpath = s.substring(l.get(i), start);
else
newpath = s.substring(l.get(i), start) + " " + path;
back(res, newpath, l.get(i), backtrackmap, s);
}
}
public List<String> wordBreak(String s, Set<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
Map<Integer, List<Integer>> backtrackmap = new HashMap<>();
for(int i = 0; i < s.length(); i++){
for(int j = i+1; j <= s.length(); j++){
String tmp = s.substring(i,j);
if(dp[i] && wordDict.contains(tmp)) {
dp[j] = true;
List<Integer> l;
if(backtrackmap.containsKey(j))
l = backtrackmap.get(j);
else
l = new ArrayList<>();
l.add(i);
backtrackmap.put(j, l);
}
}
}
List<String> res = new ArrayList<>();
back(res, "", s.length(), backtrackmap, s);
return res;
}
}
public class Solution {
ArrayList<Integer>[] P;
char[] S;
ArrayList<String> rt;
void joinAll(int offset, LinkedList<String> parents){
if(P[offset].isEmpty()){
rt.add(String.join(" ", parents));
return;
}
for(Integer p : P[offset]){
parents.push(new String(S, p, offset - p));
joinAll(p, parents);
parents.pop();
}
}
public List<String> wordBreak(String s, Set<String> dict) {
S = s.toCharArray();
P = new ArrayList[S.length + 1];
P[0] = new ArrayList<Integer>();
for(int i = 0; i < S.length; i++){
for(int j = 0; j <= i; j++){
String w = new String(S, j, i - j + 1);
if(P[j] != null && dict.contains(w)){
if(P[i + 1] == null){
P[i + 1] = new ArrayList<Integer>();
}
P[i + 1].add(j);
}
}
}
rt = new ArrayList<String>();
if(P[S.length] != null){
joinAll(S.length, new LinkedList<String>());
}
return rt;
}
}