LeetCode -- 131.分割回文串

news/发布时间2024/9/20 7:59:38

1. 问题描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。回文串是正着读和反着读都一样的字符串。

示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

2. 思路一（回溯法暴力搜索）

将字符串s的所有分割方式都搜索出来，然后一个一个判断是否满足回文串的条件，即可求得答案。那么，如何表示分割方式且回溯求得所有分割方式呢？

拿示例1举例，字符串s = "aab，初始化列表path为空。

先看第一个字符a，由于他是第一个字符，所以他无法和之前的字符（因为没有）结合，所以他单独加入path，此时path为[“a”]。第一个字符完成。

之后看第二个字符a，他就有两种选择。

与之前的字符a合并，此时代表再字符串的第二个字符处进行分割，那么此时path为[”aa“]
不与之前的字符合并，单独加入path，此时代表再字符串的第一个字符以及第二个字符都进行分割，此时path为[“a”, “a”]

继续看第三个字符、第四个字符。。。。。。直到字符串结束。这样就完成了暴力搜索。

代码如下：

public List<List<String>> partition(String s) {//存放结果List<List<String>> res = new ArrayList<>();//特殊情况if(s == null || s.length() == 0) {return res;}//存放当前分割结果List<String> path = new ArrayList<>();//递归搜索dfs(res, s, path, 0, 0);return res;}//depth表示当前在判断字符串s的第depth+1个字符，start记录上一个字符在path中的位置，因为当前字符可能需要与上一个字符拼接private void dfs(List<List<String>> res, String s, List<String> path, int depth, int start) {//如果最后一个字符也已经加入path，且满足都是回文串的条件，则把此时的path加入到结果res中if(depth == s.length()) {if(isTrue(path)) {res.add(new ArrayList<>(path));}return;}for (int i = start; i < path.size(); i++) {String str = path.get(i);str += s.charAt(depth);path.set(i, str);dfs(res, s, path, depth + 1, i);str = str.substring(0, str.length() - 1);path.set(i, str);}path.add(String.valueOf(s.charAt(depth)));dfs(res, s, path, depth + 1, path.size() - 1);path.remove(path.size() - 1);}private boolean isTrue(List<String> path) {for (String s : path) {int start = 0;int end = s.length() - 1;while (start < end) {if (s.charAt(start) == s.charAt(end)) {start++;end--;} else {return false;}}}return true;}

但这种思路只在最后进行条件判断，因此需要将所有情况遍历一遍，耗时较久

那么，在这个基础上进行改进，则是在遍历时，就加入条件判断，提前将不满足的情况去除，减小递归次数。

3. 思路二（回溯法 + 剪枝）

由于条件要求所有子串要都满足回文串的条件，因此我们对字符串s进行遍历，只有当当前子串满足回文串，才会接着考虑之后的字符。

还是拿示例一“aab”举例。

首先看第一个字符a，字符a满足回文串，那么递归考虑剩下的字符串“ab”。

同理，对于ab，也是先考虑第一个字符”a“，符合条件，考虑剩下的“b"。b也满足条件，那么此时递归完成，得到一个答案[“a”, “a”, “b”]。
考虑ab的第二个字符，此时子串”ab“不满足回文串条件，也就是说当前分割[“a”, “ab”]不满足条件，之后的字符串也不考虑，结束。

接着看第二个字符。此时当前第一个子串就是前两个字符”aa“，也满足回文串的条件，那么接着考虑剩下的字符"b"，显然b也满足，因此，此时得到一个答案[“aa”, “b”]。

之后看第三个字符。此时当前子串是”aab“，不满足回文串条件，直接结束。

此时由于已经将字符串的所有字符都考虑结束，结束搜索，一共有两个答案。

代码如下：

public List<List<String>> partition(String s) {List<List<String>> res = new ArrayList<>();if(s == null || s.length() == 0) {return res;}List<String> path = new ArrayList<>();dfs(s, 0, res, path);return res;}//start表示当前在考虑字符串s的第start+1个字符private void dfs(String s, int start, List<List<String>> res, List<String> path) {if(start == s.length()) {res.add(new ArrayList<>(path));return;}for (int i = start; i < s.length(); i++) {//如果当前下标从start到i的子串满足回文串条件，回溯搜索剩余的子串，即下标从i+1开始if(isPalindrome(s, start, i)) {//更新path，将子串加入当前分割结果path.add(s.substring(start, i + 1));dfs(s, i + 1, res, path);//回溯结束，状态重置path.remove(path.size() - 1);}}}//判断当前字符串s中，下标从start到end的子串是否为回文串private boolean isPalindrome(String s, int start, int end) {while (start <= end) {if(s.charAt(start) == s.charAt(end)) {start++;end--;}else {return false;}}return true;}