LeetCode 131 Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return [ ["aa","b"], ["a","a","b"]]
和combination，permutation类似可以使用backtracing或dp，对于这类题backtracing的方法比较熟，所以直接回溯实现了。
submit了三遍才AC，发现是isPalindrome里有一个小错误。。。
代码：
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<List<String>>();
if (s.length() == 0) return res;
partitionRecursive(s, 0, new ArrayList<String>(), res);
return res;
}
public boolean isPalindrome(String str) {
int st = 0, ed = str.length()-1;
while (st < ed) {
if (str.charAt(st) != str.charAt(ed)) return false;
st++;
ed--;
}
return true;
}
public void partitionRecursive(String s, int index, List<String> p, List<List<String>> res) {
if (index == s.length()) {
res.add(new ArrayList(p));
return;
}
for (int i = index+1; i <= s.length(); i++) {
String str = s.substring(index, i);
if (isPalindrome(str)) {
p.add(str);
partitionRecursive(s, i, p, res);
p.remove(p.size()-1);
}
}
}
}
