Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input:"aab"Output:[ ["aa","b"], ["a","a","b"]]
这题一开始想法是每个字符有两种情况：加到当前字符串，或加到下一个字符串。后来看了下别人的答案，其实直接先判断是否回文，再进行list的add操作，更省时间。
class Solution {
public List<List<String>> partition(String s) {
// System.out.println("input: " + s);
List<List<String>> res = new LinkedList<>();
LinkedList<String> cur = new LinkedList<String>();
backtrace(cur, res, s, 0);
return res;
}
private void backtrace(LinkedList<String> cur, List<List<String>> res, String s, int index) {
// System.out.println(String.format("cur: %s, index: %d, s: %s", Arrays.deepToString(cur.toArray()), index, s));
if (index == s.length()) {
res.add(new ArrayList<>(cur));
return;
}
for (int r = index; r < s.length(); r++) {
if (isPalindrome(s, index, r)) {
cur.add(s.substring(index, r + 1));
backtrace(cur, res, s, r + 1);
cur.removeLast();
}
}
}
private boolean isPalindrome(String s, int l, int r) {
while (l < r) {
if (s.charAt(l) != s.charAt(r)) return false;
l++; r--;
}
return true;
}
}
还要吐槽leetcode，这题我完全一样的答案，提交上去有时候4ms，有时候2ms，弄得百分比也不一样，还以为代码还有哪里有问题，结果拷贝了2ms的答案跑出来也要5ms左右
