分割回文串

七崽爱吃小饼干2026/01/30阅读 0

分割回文串

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

示例 1：

codeType

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
解释：s可以拆分成a、a、b和aa、b两种全是回文子串的结果

示例 2：

codeType

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

提示：

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

解法

这题需要用到动态规划+回溯

在查找最长回文子串中就曾学习过如何用动态规划判断子串是否为回文串。

此外还需要用回溯法逐个查找分割的方案。

function partition(s: string): string[][] {
    // 按动态规划的思路有
    // F[i][j]表示子串i-j是否是回文串
    // 所以F[i][j] = F[i+1][j-1] && s[i] === s[j]
    // 要从对角线往外进行遍历，也就是l = 1 =》l = n
    // 然后就能在O(1)的时间内判断F[i][j]是否是回文串了
    // 再通过回溯法，逐个查找方案
    const n = s.length
    const dp = new Array(n).fill(0).map(() => new Array(n).fill(false))
    for(let len = 1; len <= n; len++){
        for(let i = 0; i < n; i++){ // 从第0个位置开始查找长为len的子串
            const j = i + len - 1 // j的值
            if(j >= n) break // j越界
            // len==1或len==2需要单独判断
            if(len === 1){
                dp[i][j] = true
                continue
            }
            if(len === 2 && s[i] === s[j]){
                dp[i][j] = true
                continue
            }
            if(dp[i + 1][j - 1] && s[i] === s[j]){
                dp[i][j] = true
            }
        }
    }
    const res = []
    // 分割组合的意思就是，把原串拆成几个子串，子串都是回文串。
    const helper = (preStr: string[], startIndex: number) => {
        if(startIndex === n){
            // 划分到最后了
            res.push([...preStr])
            return
        }
        
        // 接下来的子串分割要接着之前分割串的右边继续
        // 也就是说，接下来要划分startIndex-j的子串
        for(let j = startIndex; j < n; j++){
            if(dp[startIndex][j]){
                preStr.push(s.slice(startIndex, j + 1))
                helper(preStr, j + 1) // 下次划分从j+1开始
                preStr.pop() // 回溯
            }
        }
    }
    helper([],0)
    return res
};