leetcode131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
思路：搜索回溯，搜索过程中检查是否是回文。
public class Solution {
List<List> res = new ArrayList();
// Stack 这个类 Java 的文档里推荐写成 Deque stack = new ArrayDeque();
// 注意：只使用 stack 相关的接口
Deque stack = new ArrayDeque();
int len;
public List<List> partition(String s) {
len = s.length();
if (len == 0) return res;
backtracking(s, 0);
return res;
}
private void backtracking(String s, int start) {
if (start == len) {
res.add(new ArrayList(stack));
return;
}
for (int i = start; i < len; i++) {
if (checkPalindrome(s, start, i)) {
stack.addLast(s.substring(start, i + 1));
backtracking(s, i + 1);
stack.removeLast();
}
}
}
private boolean checkPalindrome(String str, int left, int right) {
while (left < right) {
if (str.charAt(left) != str.charAt(right)) return false;
left++;right--;
}
return true;
}
}
作者：一只大白兔兔兔兔兔
