leetcode热题HOT leetcode131. 分割回文串

本文主要是介绍leetcode热题HOT leetcode131. 分割回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
本题属于分割问题，for循环的暴力解法太耗时了 ，不太现实。考虑另一种暴力解法-回溯。这里可以参考Carl的回溯方法模板：

二、解题思路：

1. 通过递归和回溯的方式，不断尝试各种分割方式，并判断每个子串是否为回文字符串，最终得到所有满足条件的分割结果。
2. 具体步骤：
   ①定义一个全局变量 result 用于存储最终的结果，path 用于存储当前路径上的子串。
   ②partition 方法是整个算法的入口，它调用 partitions 方法进行递归分割。
   ③partitions 方法的作用是从位置 l 开始向后遍历字符串 s，对于每一个可能的子串，如果是回文字符串，则将其加入到 path 中，并递归处理剩余部分，最后将该子串移出 path。这样可以找出所有满足条件的分割情况。
   ④huiwen 方法用于判断字符串 s 中从位置 l 到位置 r 的子串是否为回文字符串，通过双指针法来进行判断。
   ⑤在递归过程中，不断尝试各种分割方式，并且在满足条件时将当前的路径加入到结果集中。最终返回结果集 result。
3. 注意几个关键点：
   ①找到递归的终止条件：从起始点开始分割字符串，如果分割点startindex>= s.length()，说明分割完毕，找到一组解。
   ②在for (int i = l; i < s.length(); i++)循环中，我们定义了起始位置l，那么 [l, i] 就是要截取的子串。
   ③处理节点就是要判断这个子串是不是回文串，如果是回文，就加入path中，path用来记录切割过的回文子串，然后继续分割剩余的子串，起始位置变为i+1。如果不是回文串则continue 跳过，没必要继续分割了。

三、代码示例：

class Solution {List<List<String>> result = new ArrayList<>(); // 存储最终的结果LinkedList<String> path = new LinkedList<>(); // 存储当前路径上的子串public List<List<String>> partition(String s) {partitions(s, 0); // 调用递归方法进行字符串分割return result; // 返回最终结果}// 递归方法，对字符串 s 进行分割public void partitions(String s, int l) {if (l >= s.length()) { // 如果已经遍历完整个字符串 sresult.add(new ArrayList<>(path)); // 将当前路径加入到结果集中return;}for (int i = l; i < s.length(); i++) {if (huiwen(s, l, i)) { // 如果从位置 l 到位置 i 的子串是回文字符串path.add(s.substring(l, i + 1)); // 将该子串加入到当前路径中} else {continue; // 否则继续向后遍历}partitions(s, i + 1); // 递归处理剩余部分path.removeLast(); // 回溯，将最后加入的子串移出当前路径}}// 判断字符串 s 中从位置 l 到位置 r 的子串是否为回文字符串public boolean huiwen(String s, int l, int r) {while (l < r) {if (s.charAt(l) != s.charAt(r)) {return false; // 不是回文字符串}l++;r--;}return true; // 是回文字符串}
}

• 时间复杂度分析：对于长度为 n 的字符串 s，最坏情况下有 2^n 种分割方式，因为每个字符都有可能是分割点或者不是分割点。
  在递归过程中，每一种分割情况都要判断其中的子串是否为回文字符串，这个判断操作的时间复杂度为 O(n)。
  因此，总体时间复杂度为 O(n * 2^n)，即指数级别的复杂度。

四、补充与总结：

1. 递归模板

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中的元素) {处理单个节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

2. 判断回文子串：字符串反转后和原字符串相同即为回文串，可用双指针法判断。

    private boolean huiwen(String s, int startIndex, int end) {for (int i = startIndex, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) return false;}return true;}

3. 字符串截取：通过subString()方法来进行字符串截取，返回字符串中的子字符串。

①传递一个参数：

public String substring(int beginIndex);
//子字符串从指定索引处的字符开始，到此字符串末尾。

②传递两个参数：

public String substring(int beginIndex, int endIndex);
//从指定的 beginIndex 处开始，直到索引 endIndex - 1 处的字符。因此，该子字符串的长度为 endIndex-beginIndex。
//参数说明：beginIndex – 起始索引（包括）、endIndex – 结束索引（不包括）。

这篇关于leetcode热题HOT leetcode131. 分割回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---