1745. 回文串分割 IV #

问题描述#

给你一个字符串 s ，如果可以将它分割成三个非空回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：
输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
提示：

3 <= s.length <= 2000

s 只包含小写英文字母。

解题思路#

\([i,j]\) 范围内的字符串为回文，可以通过判断 \(s[i]==s[j]\) 和 \([i+1,j-1]\) 的字符串为回文得到。

所以可以使用 DP 记录所有 \([i,j]\) 的回文情况，然后再枚举分界点即可。

C++

class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j + i - 1 < n; ++j) {
                int k = j + i - 1;
                if (s[j] == s[k] && (k - 1 < j + 1 || dp[j + 1][k - 1])) dp[j][k] = 1;
            }
        }

        for (int i = 1; i < n - 1; ++i) {
            for (int j = i; j < n - 1; ++j) {
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;
            }
        }

        return false;
    }
};

Python

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        dp = [[False for _ in range(n)] for _ in range(n)]

        for i in range(1, n + 1): # 枚举字符串长度
            for j in range(n - i + 1):
                k = j + i - 1
                if s[j] == s[k] and (k - 1 < j + 1 or dp[j + 1][k - 1]):
                    dp[j][k] = True

        for i in range(1, n - 1):
            for j in range(i, n - 1):
                if dp[0][i - 1] and dp[i][j] and dp[j + 1][n - 1]:
                    return True

        return False

时间复杂度：\(\mathcal{O}(n^2)\)
空间复杂度：\(\mathcal{O}(n^2)\)

1745. 回文串分割 IV#

问题描述#

解题思路#

1745. 回文串分割 IV #