Hard

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

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

解题思路

解题思路

这是一道经典的动态规划题目，需要找到将字符串分割成回文子串的最少分割次数。

方法一：动态规划 + 预处理（推荐）

核心思想是使用两个动态规划：

  1. 首先预处理出所有子串是否为回文串
  2. 然后用动态规划求最少分割次数

预处理阶段：

  • 使用二维数组 isPalindrome[i][j] 表示子串 s[i:j+1] 是否为回文串
  • 通过中心扩展法或区间DP预处理所有子串的回文性质

动态规划阶段：

  • 定义 dp[i] 表示字符串 s[0:i] 的最少分割次数
  • 状态转移：对于每个位置 i，枚举所有可能的分割点 j
  • 如果 s[j:i] 是回文串，则 dp[i] = min(dp[i], dp[j] + 1)

方法二：中心扩展优化

在计算最少分割次数的同时，使用中心扩展法动态判断回文串，可以节省空间。

时间复杂度：O(n²)，空间复杂度：O(n²)（预处理）或O(n)（中心扩展）

代码实现

class Solution {
public:
    int minCut(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;
                }
            }
        }
        
        // 动态规划求最少分割次数
        vector<int> dp(n, INT_MAX);
        
        for (int i = 0; i < n; i++) {
            if (isPalindrome[0][i]) {
                dp[i] = 0;  // 整个前缀都是回文串，不需要分割
            } else {
                for (int j = 0; j < i; j++) {
                    if (isPalindrome[j + 1][i]) {
                        dp[i] = min(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
};

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        
        # 预处理：判断所有子串是否为回文串
        is_palindrome = [[False] * n for _ in range(n)]
        
        # 单个字符都是回文串
        for i in range(n):
            is_palindrome[i][i] = True
        
        # 长度为2的子串
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                is_palindrome[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 is_palindrome[i + 1][j - 1]:
                    is_palindrome[i][j] = True
        
        # 动态规划求最少分割次数
        dp = [float('inf')] * n
        
        for i in range(n):
            if is_palindrome[0][i]:
                dp[i] = 0  # 整个前缀都是回文串，不需要分割
            else:
                for j in range(i):
                    if is_palindrome[j + 1][i]:
                        dp[i] = min(dp[i], dp[j] + 1)
        
        return dp[n - 1]

public class Solution {
    public int MinCut(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;
                }
            }
        }
        
        // 动态规划求最少分割次数
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);
        
        for (int i = 0; i < n; i++) {
            if (isPalindrome[0, i]) {
                dp[i] = 0;  // 整个前缀都是回文串，不需要分割
            } else {
                for (int j = 0; j < i; j++) {
                    if (isPalindrome[j + 1, i]) {
                        dp[i] = Math.Min(dp[i], dp[j] + 1);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
}

var minCut = 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²)
  • 空间复杂度：需要 O(n²) 的空间存储回文串判断结果，以及 O(n) 的空间存储dp数组

相关题目