leetcode131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"

输出:

[

["aa","b"],

["a","a","b"]

]

思路：搜索回溯，搜索过程中检查是否是回文。

public class Solution {

List> res = new ArrayList<>();

// Stack 这个类 Java 的文档里推荐写成 Deque stack = new ArrayDeque();

// 注意：只使用 stack 相关的接口

Deque stack = new ArrayDeque<>();

int len;

public 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;

}

}

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。