Leetcode 分割回文串

时间：2024-10-20 12:12:26

在这里插入图片描述

算法思想

1. 回溯法 (Backtracking)：

  • 回溯法是一种通过递归去尝试所有可能的解，并在每次递归中做出选择、回溯的策略。
  • 在这道题中，我们需要通过回溯法来生成字符串的所有可能分割方式，并判断每个分割的子串是否为回文。

2. 分割与判断：

  • 首先，我们从字符串的第一个字符开始，依次检查从第一个字符到当前字符构成的子串是否为回文。
  • 如果当前子串是回文串，就可以继续尝试从这个子串的结尾位置向后继续分割剩下的部分。
  • 如果遍历完所有字符并且成功将字符串分割为回文子串（即字符串遍历完时，所有分割都是回文），就将这种分割方案保存起来。

3. 递归与回溯：

  • backtrack 方法是递归函数，用来从当前字符开始向后尝试不同的分割方法。
  • 每次找到一个回文串后，将其加入当前的结果列表 (currentList)，然后递归处理剩下的部分。
  • 当递归到字符串结尾（即 start == s.length()），说明找到了一种合法的分割方式，这时将当前的分割方式保存到最终结果 result 中。
  • 当回溯返回时，撤销之前的选择，即将最后加入的回文串从列表中移除 (currentList.remove(currentList.size() - 1))，从而继续寻找其他可能的分割方案。

4. 判断回文串：

  • 在 isPalindrome 方法中，通过双指针（从字符串两端向中间遍历）来判断某个子串是否是回文。
  • 只要发现左右两端字符不相等，就可以确定该子串不是回文，立即返回 false，否则继续判断直到中间。

代码执行过程（以 “aab” 为例）：

  • 输入字符串 s = "aab"。
  • 第一次递归从第一个字符开始，先检查子串 "a" 是否为回文，发现是回文，于是将 "a" 放入当前的分割列表，然后递归处理剩下的子串 "ab"。
  • 在处理 "ab" 时，首先检查 "a"，也是回文，于是继续递归处理 "b"。发现 "b" 也是回文，递归结束，得到一种分割方案 ["a", "a", "b"]。
  • 回溯后，移除最后的 "b"，然后继续尝试检查 "ab"，发现不是回文，无法进行分割。
  • 继续回溯到最外层，移除 "a"，然后尝试检查前两个字符 "aa"，发现是回文，于是递归处理剩下的 "b"，得到另一种分割方案 ["aa", "b"]。
  • 递归结束，最终返回所有的分割结果。

复杂度分析：

  • 时间复杂度： 最坏情况下，每个子串都可能是回文，所以需要遍历所有可能的分割方式，时间复杂度大致为 O(n * 2^n)，其中 n 是字符串的长度。
  • 空间复杂度： 由于递归深度取决于字符串的长度，因此空间复杂度为 O(n)。

总结：

这个算法通过回溯法，递归地生成所有可能的子串分割，并通过逐个判断子串是否为回文来过滤合法的分割方案。

java solution

class Solution {
    public List<List<String>> partition(String s) {
        //result包含所有可能的回文分割方案
        List<List<String>> result = new ArrayList<>();
        //currentList代表某一种可能的回文分割方案
        List<String> currentList = new ArrayList<>();
        backtrack(result, currentList, s, 0);
        return result;
    }
    private void backtrack(List<List<String>> result, List<String> currentList, String s, int start) {
        if(start == s.length()) {
            result.add(new ArrayList<>(currentList));
            return; //这里必须return,递归终止条件
        }
        for(int i = start; i < s.length(); ++i) {
            if(isPalindrome(s, start, i)) {
                currentList.add(s.substring(start, i + 1)); //添加了一个回文子串,currentList.size()增加1
                backtrack(result, currentList, s, i + 1);
                currentList.remove(currentList.size() - 1); //撤销上个回文子串的选择
            }
        }

    }
    private boolean isPalindrome(String s, int low, int high) {
        while(low < high) {
            if(s.charAt(low) != s.charAt(high)) {
                return false;
            }
            low++;//注意更新左右指针！！
            high--;
        }
        return true;
    }
}

相关文章