LeetCode 131. 分割回文串_给定一个字符串 s ,请将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可

131. 分割回文串

题目描述

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

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

示例 1：

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

示例 2：

输入：s = “a”
输出：[[“a”]]

解题思路

思路一： 回溯

1. 从index = 0 开始枚举子串， 如果子串是回文串，就将该子串添加到path(path 的操作只在列表的末端，因此合适的数据结构是栈)中，并从该子串的后一个索引位置开始继续枚举；
2. 当 index 越界，回溯结束， 我们将path加入到res中（注意： path是个引入对象）； 在退出某一层递归时，记得在path中删除该层递归添加的子串（这是一个先递归到最底层，然后一层一层向上的回溯的过程）

实现代码如下：

/**
 * @param {string} s
 * @return {string[][]}
 */
 var partition = function(s) {
    let len = s.length, stack = [], res = [];
    dfs(s, 0, len, stack, res);
    return res;
};

const dfs = function (str, index, len, path, res) {
    if (index == len) {
        res.push([...path]);
        return; 
    }
    for (let i = index; i < len; i++) {
        if(!checkPalindrome(str, index, i)) {
            continue;
        }
        path.push(str.substr(index, i + 1 - index));
        dfs(str, i + 1, len, path, res);
        path.pop()
    }
}

// 辅助方法， 判断从left到right是否回文
const checkPalindrome = function (str, left, right) {
    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

• 时间复杂度： $O(n\ast 2^n)$, 这里 n 为输入字符串的长度，每一个位置可拆分，也可不拆分，尝试是否可以拆分的时间复杂度为 $O(2^N)$，判断每一个子串是否是回文子串，时间复杂度为 O(n) ;
• 空间复杂度：$O(2^n)$，返回结果最多有 $O(2^n)$种划分方法

思路二： 回溯的优化（使用动态规划得到所有子串是否是回文）

状态转移方程： dp[i][j] = s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])

实现代码如下：

/**
 * @param {string} s
 * @return {string[][]}
 */
 var partition = function(s) {
    let len = s.length, 
        // 状态：dp[i][j] 表示 s[i][j] 是否是回文
        dp = Array.from(Array(len), () => Array(len).fill(false)),
        res = [];
    // 状态转移方程：在 s[i] == s[j] 的时候，dp[i][j] 参考 dp[i + 1][j - 1]
    for (let right = 0; right < len; right++) {
        // 注意：left <= right 取等号表示 1 个字符的时候也需要判断
        for (let left = 0; left <= right; left++) {
            if (s[left] == s[right] && (right - left <= 2 || dp[left + 1][right - 1])) {
                dp[left][right] = true;
            }
        }
    }
    let stack = [];
    dfs(s, 0, len, dp, stack, res);
    return res;

};

const dfs = function (s, index, len, dp, path, res) {
    if (index == len) {
        res.push([...path]);
        return;
    }

    for (let i = index; i < len; i++) {
        if (dp[index][i]) {
            path.push(s.substr(index, i + 1 - index));
            dfs(s, i + 1, len, dp, path, res);
            path.pop();
        }
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

• 时间复杂度：$O(2^n)$ ；这里 n 为输入字符串的长度，每一个位置可拆分，也可不拆分，尝试是否可以拆分的时间复杂度为 $O(2^n)$，动态规划得到所有子串是否为回文子串的时间复杂度为 $O(n^2)$ ，所以总的时间复杂度为 $O(n^2+2^n)=O(2^N)$
• 空间复杂度： 计算保存答案需要空间 $2^N\times N$

参考资料

https://leetcode.cn/problems/palindrome-partitioning/solution/hui-su-you-hua-jia-liao-dong-tai-gui-hua-by-liweiw/