Medium

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

这是一个经典的回溯算法问题。我们需要找到字符串的所有可能分割方案，使得每个子串都是回文串。

主要思路：

  1. 使用回溯算法枚举所有可能的分割位置
  2. 对于每个位置，检查从当前起始位置到该位置的子串是否为回文串
  3. 如果是回文串，则将其加入当前路径，继续递归处理剩余部分
  4. 当处理完整个字符串时，将当前路径加入结果集

优化策略： 为了避免重复计算回文串判断，我们可以预处理所有子串的回文性质，使用动态规划构建一个二维布尔数组 dp[i][j] 表示从索引 i 到 j 的子串是否为回文串。

算法步骤：

  1. 预处理：使用动态规划计算所有子串是否为回文
  2. 回溯：从字符串起始位置开始，尝试每一个可能的分割点
  3. 递归：对每个有效的回文子串，递归处理剩余部分
  4. 回退：撤销当前选择，尝试下一个可能性

代码实现

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[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
                    dp[j][i] = true;
                }
            }
        }
        
        vector<vector<string>> result;
        vector<string> path;
        backtrack(s, 0, dp, path, result);
        return result;
    }
    
private:
    void backtrack(const string& s, int start, const vector<vector<bool>>& dp, 
                   vector<string>& path, vector<vector<string>>& result) {
        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, dp, path, result);
                path.pop_back();
            }
        }
    }
};

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[i] == s[j] and (i - j <= 2 or dp[j + 1][i - 1]):
                    dp[j][i] = True
        
        result = []
        path = []
        
        def backtrack(start):
            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.pop()
        
        backtrack(0)
        return result

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[i] == s[j] && (i - j <= 2 || dp[j + 1, i - 1])) {
                    dp[j, i] = true;
                }
            }
        }
        
        IList<IList<string>> result = new List<IList<string>>();
        IList<string> path = new List<string>();
        Backtrack(s, 0, dp, path, result);
        return result;
    }
    
    private void Backtrack(string s, int start, bool[,] dp, 
                          IList<string> path, IList<IList<string>> result) {
        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, dp, path, result);
                path.RemoveAt(path.Count - 1);
            }
        }
    }
}

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const result = [];
    const current = [];
    
    const isPalindrome = (str, left, right) => {
        while (left < right) {
            if (str[left] !== str[right]) return false;
            left++;
            right--;
        }
        return true;
    };
    
    const backtrack = (start) => {
        if (start === s.length) {
            result.push([...current]);
            return;
        }
        
        for (let end = start; end < s.length; end++) {
            if (isPalindrome(s, start, end)) {
                current.push(s.substring(start, end + 1));
                backtrack(end + 1);
                current.pop();
            }
        }
    };
    
    backtrack(0);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(N × 2^N)预处理需要O(N²)，回溯过程最多有2^N种分割方案，每种方案需要O(N)时间复制
空间复杂度O(N²)dp数组需要O(N²)空间，递归栈深度最多为N

相关题目