Hard

题目描述

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

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

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文串。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 无法分割成 3 个回文串。

提示：

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

提示：

  • 预处理回文检查可以做到 O(1)
  • 注意一个字符串是前缀，另一个是后缀，你可以尝试暴力搜索剩余部分

解题思路

解题思路

这道题要求将字符串分割成恰好三个回文子字符串。我们可以采用预处理 + 枚举的方法来解决。

核心思路

  1. 预处理回文信息：使用动态规划预处理所有子字符串的回文性质，这样可以在 O(1) 时间内判断任意子字符串是否为回文串。

  2. 枚举分割点：枚举两个分割点 i 和 j（i < j），将字符串分成三部分：

    • 第一部分：s[0…i-1]
    • 第二部分：s[i…j-1]
    • 第三部分：s[j…n-1]

  3. 验证方案：检查这三个部分是否都是回文串，如果是则返回 true。

预处理优化

使用二维 DP 数组 isPalindrome[i][j] 表示 s[i…j] 是否为回文串：

  • 如果 s[i] == s[j] 且 s[i+1…j-1] 是回文串，则 s[i…j] 也是回文串
  • 单个字符和相邻相同字符都是回文串

时间复杂度分析

  • 预处理：O(n²)
  • 枚举分割点：O(n²)
  • 总体：O(n²)

这种方法避免了重复的回文检查，大大提升了效率。

代码实现

class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.length();
        
        // 预处理：计算所有子字符串的回文性质
        vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
        
        // 单个字符都是回文
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        
        // 长度为2的字符串
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                isPalindrome[i][i + 1] = true;
            }
        }
        
        // 长度大于2的字符串
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && isPalindrome[i + 1][j - 1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }
        
        // 枚举两个分割点
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPalindrome[0][i - 1] && 
                    isPalindrome[i][j - 1] && 
                    isPalindrome[j][n - 1]) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def checkPartitioning(self, s: str) -> bool:
        n = len(s)
        
        # 预处理：计算所有子字符串的回文性质
        isPalindrome = [[False] * n for _ in range(n)]
        
        # 单个字符都是回文
        for i in range(n):
            isPalindrome[i][i] = True
        
        # 长度为2的字符串
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                isPalindrome[i][i + 1] = True
        
        # 长度大于2的字符串
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and isPalindrome[i + 1][j - 1]:
                    isPalindrome[i][j] = True
        
        # 枚举两个分割点
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                if (isPalindrome[0][i - 1] and 
                    isPalindrome[i][j - 1] and 
                    isPalindrome[j][n - 1]):
                    return True
        
        return False

public class Solution {
    public bool CheckPartitioning(string s) {
        int n = s.Length;
        
        // 预处理：计算所有子字符串的回文性质
        bool[,] isPalindrome = new bool[n, n];
        
        // 单个字符都是回文
        for (int i = 0; i < n; i++) {
            isPalindrome[i, i] = true;
        }
        
        // 长度为2的字符串
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                isPalindrome[i, i + 1] = true;
            }
        }
        
        // 长度大于2的字符串
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && isPalindrome[i + 1, j - 1]) {
                    isPalindrome[i, j] = true;
                }
            }
        }
        
        // 枚举两个分割点
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isPalindrome[0, i - 1] && 
                    isPalindrome[i, j - 1] && 
                    isPalindrome[j, n - 1]) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

var checkPartitioning = function(s) {
    const n = s.length;
    
    // 预处理：计算所有子字符串的回文性质
    const isPalindrome = Array(n).fill().map(() => Array(n).fill(false));
    
    // 单个字符都是回文
    for (let i = 0; i < n; i++) {
        isPalindrome[i][i] = true;
    }
    
    // 长度为2的字符串
    for (let i = 0; i < n - 1; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)预处理回文信息需要 O(n²)，枚举分割点需要 O(n²)
空间复杂度O(n²)需要二维数组存储所有子字符串的回文信息

相关题目