leetcode里的Palindrome partition问题# JobHunting - 待字闺中
g*n
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;
}
partition.remove(partition.size() - 1);
为什么每次递归调用后需要把最后一个删掉呢？
谢谢
public ArrayList
ArrayList
if (s == null || s.length() == 0) {
return result;
}
ArrayList
addPalindrome(s, 0, partition, result);
return result;
}
private void addPalindrome(String s, int start, ArrayList
ArrayList
//stop condition
if (start == s.length()) {
ArrayList
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;
}
