05 August 2008
给一个string，分成若干sub strings，使每个substring都是回文，返回所有可能性
Topdown
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
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
dp[j][i] = true;
}
}
}
helper(res, new ArrayList<>(), dp, s, 0);
return res;
}
private void helper(List<List<String>> res, List<String> path, boolean[][] dp, String s, int pos) {
if(pos == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for(int i = pos; i < s.length(); i++) {
if(dp[pos][i]) {
path.add(s.substring(pos,i+1));
helper(res, path, dp, s, i+1);
path.remove(path.size()-1);
}
}
}
}
DP
result[0..right] = result[0..left-1] + s[left..right] if s[left..right] is a palindrome
p[left,right] = true if right-left<=1 or s[left] == s[right] && p[left+1,right-1]
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
class Solution {
public static List<List<String>> partition(String s) {
int len = s.length();
List<List<String>>[] result = new List[len + 1];
result[0] = new ArrayList<List<String>>();
result[0].add(new ArrayList<String>());
boolean[][] pair = new boolean[len][len];
for (int i = 0; i < s.length(); i++) {
result[i + 1] = new ArrayList<List<String>>();
for (int left = 0; left <= i; left++) {
if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])) {
pair[left][i] = true;
String str = s.substring(left, i + 1);
for (List<String> r : result[left]) {
List<String> ri = new ArrayList<String>(r);
ri.add(str);
result[i + 1].add(ri);
}
}
}
}
return result[len];
}
}