g********n
发帖数: 447 | 1 网上找了一个solution是用dp的，可是这里怎么也想不明白，能指点一下吗？谢谢
partition.remove(partition.size() - 1);
为什么每次递归调用后需要把最后一个删掉呢？
谢谢
public ArrayList> partition(String s) {
ArrayList> result = new ArrayList>();
if (s == null || s.length() == 0) {
return result;
}
ArrayList partition = new ArrayList();
addPalindrome(s, 0, partition, result);
return result;
}
private void addPalindrome(String s, int start, ArrayList partition,
ArrayList> result) {
//stop condition
if (start == s.length()) {
ArrayList temp = new ArrayList(partition);
result.add(temp);
return;
}
for (int i = start + 1; i <= s.length(); i++) {
String str = s.substring(start, i);
if (isPalindrome(str)) {
partition.add(str);
addPalindrome(s, i, partition, result);
partition.remove(partition.size() - 1);
}
}
}
private boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
} | a***n
发帖数: 623 | 2 我觉得面试要考这道题让你写代码，那成心就想挂你…… | l*****a
发帖数: 14598 | 3 你夸张了
这个不就是写组合吗，要求组合里每个都是palindrome
基本算brute force吧
【在 a***n 的大作中提到】
: 我觉得面试要考这道题让你写代码，那成心就想挂你……
| a***n
发帖数: 623 | 4 不好意思，记错了，想成Longest Palindromic Substring那题了
【在 l*****a 的大作中提到】
: 你夸张了
: 这个不就是写组合吗，要求组合里每个都是palindrome
: 基本算brute force吧
| b******t
发帖数: 965 | 5 我觉得leetcode很多题都这样啊 当然练过几遍还是能写的出来的
不过很多题如果没练过连思路都不一定有
【在 a***n 的大作中提到】
: 我觉得面试要考这道题让你写代码，那成心就想挂你……
| w*******y
发帖数: 64 | |
|
