LeetCode第131题_分割回文串

LeetCode 第131题：分割回文串

题目描述

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

回文串 是正着读和反着读都一样的字符串。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

解题思路

方法一：回溯 + 动态规划预处理

这道题要求将字符串分割成回文子串，并返回所有可能的分割方案。我们可以使用回溯算法来解决这个问题。

关键点：

• 使用回溯算法枚举所有可能的分割方案
• 使用动态规划预处理判断子串是否为回文串，避免重复计算
• 递归构建分割方案，当处理完整个字符串时，将当前方案加入结果集

具体步骤：

1. 使用动态规划预处理，计算字符串的所有子串是否为回文串
   • 定义dp[i][j]表示s[i…j]是否为回文串
   • 状态转移方程：dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1])
2. 使用回溯算法枚举所有可能的分割方案
   • 定义递归函数backtrack(start, path)，其中start表示当前处理的起始位置，path表示当前的分割方案
   • 如果start等于字符串长度，说明已经处理完整个字符串，将当前方案加入结果集
   • 否则，枚举从start开始的所有可能的子串，如果是回文串，则将其加入当前方案，并递归处理剩余部分

时间复杂度：O(n * 2^{n)，其中n是字符串的长度。在最坏情况下，字符串中的每个字符都可以作为一个回文串，因此有2}n种可能的分割方式，每种分割方式需要O(n)的时间来构建。
空间复杂度：O(n^{2)，需要O(n}2)的空间存储动态规划的结果，以及O(n)的递归调用栈空间。

方法二：回溯 + 中心扩展法

另一种解决方案是使用回溯算法结合中心扩展法来判断回文串。

关键点：

• 使用回溯算法枚举所有可能的分割方案
• 使用中心扩展法判断子串是否为回文串
• 递归构建分割方案，当处理完整个字符串时，将当前方案加入结果集

具体步骤：

1. 定义一个函数isPalindrome(s, start, end)，使用中心扩展法判断子串是否为回文串
2. 使用回溯算法枚举所有可能的分割方案
   • 定义递归函数backtrack(start, path)，其中start表示当前处理的起始位置，path表示当前的分割方案
   • 如果start等于字符串长度，说明已经处理完整个字符串，将当前方案加入结果集
   • 否则，枚举从start开始的所有可能的子串，如果是回文串，则将其加入当前方案，并递归处理剩余部分

时间复杂度：O(n * 2^{n)，其中n是字符串的长度。在最坏情况下，字符串中的每个字符都可以作为一个回文串，因此有2}n种可能的分割方式，每种分割方式需要O(n)的时间来构建。
空间复杂度：O(n)，递归调用栈的最大深度为n。

图解思路

回溯过程分析表

以示例1为例：s = “aab”

动态规划预处理表

代码实现

C# 实现

public class Solution {
    public IList<IList<string>> Partition(string s) {
        int n = s.Length;
        // 动态规划预处理
        bool[,] dp = new bool[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s[j] == s[i] && (i - j <= 2 || dp[j + 1, i - 1])) {
                    dp[j, i] = true;
                }
            }
        }
        
        IList<IList<string>> result = new List<IList<string>>();
        Backtrack(s, 0, new List<string>(), result, dp);
        return result;
    }
    
    private void Backtrack(string s, int start, IList<string> path, IList<IList<string>> result, bool[,] dp) {
        if (start == s.Length) {
            result.Add(new List<string>(path));
            return;
        }
        
        for (int end = start; end < s.Length; end++) {
            if (dp[start, end]) {
                path.Add(s.Substring(start, end - start + 1));
                Backtrack(s, end + 1, path, result, dp);
                path.RemoveAt(path.Count - 1);
            }
        }
    }
}

Python 实现

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # 动态规划预处理
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1):
                if s[j] == s[i] and (i - j <= 2 or dp[j + 1][i - 1]):
                    dp[j][i] = True
        
        result = []
        
        def backtrack(start, path):
            if start == n:
                result.append(path[:])
                return
            
            for end in range(start, n):
                if dp[start][end]:
                    path.append(s[start:end + 1])
                    backtrack(end + 1, path)
                    path.pop()
        
        backtrack(0, [])
        return result

C++ 实现

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.length();
        // 动态规划预处理
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (s[j] == s[i] && (i - j <= 2 || dp[j + 1][i - 1])) {
                    dp[j][i] = true;
                }
            }
        }
        
        vector<vector<string>> result;
        vector<string> path;
        backtrack(s, 0, path, result, dp);
        return result;
    }
    
private:
    void backtrack(const string& s, int start, vector<string>& path, vector<vector<string>>& result, const vector<vector<bool>>& dp) {
        if (start == s.length()) {
            result.push_back(path);
            return;
        }
        
        for (int end = start; end < s.length(); end++) {
            if (dp[start][end]) {
                path.push_back(s.substr(start, end - start + 1));
                backtrack(s, end + 1, path, result, dp);
                path.pop_back();
            }
        }
    }
};

执行结果

C# 实现

• 执行用时：432 ms
• 内存消耗：67.2 MB

Python 实现

• 执行用时：128 ms
• 内存消耗：30.4 MB

C++ 实现

• 执行用时：92 ms
• 内存消耗：74.8 MB

性能对比

代码亮点

1. 🎯 使用动态规划预处理判断回文串，避免重复计算
2. 💡 回溯算法清晰地枚举所有可能的分割方案
3. 🔍 剪枝优化，只有当子串是回文串时才继续递归
4. 🎨 代码结构清晰，逻辑简单易懂

常见错误分析

1. 🚫 回溯过程中忘记回溯（移除最后一个元素），导致结果错误
2. 🚫 动态规划预处理的状态转移方程错误，导致判断回文串不正确
3. 🚫 递归终止条件设置不正确，导致无法正确构建分割方案
4. 🚫 字符串截取范围错误，导致子串不正确

解法对比

相关题目

• LeetCode 132. 分割回文串 II - 困难
• LeetCode 93. 复原 IP 地址 - 中等
• LeetCode 139. 单词拆分 - 中等
• LeetCode 140. 单词拆分 II - 困难
• LeetCode 5. 最长回文子串 - 中等