[LeetCode] 每日一题 132. 分割回文串 II

题目链接

https://leetcode.cn/problems/palindrome-partitioning-ii

题目描述

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

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

回文 串是向前和向后读都相同的字符串。

示例输入

示例 1

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

示例 2

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

示例 3

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

提示

• 1 <= s.length <= 2000

• s 仅由小写英文字母组成

解题思路

本题要求将字符串 s 分割成若干回文子串，并返回最少的分割次数。相比昨天的题目（返回所有可能的分割方案），这道题的思路更加单一，主要依赖动态规划来解决

首先，使用动态规划预处理字符串的回文情况，即 dp[i][j] 表示 s[i:j] 是否是回文串。判断方式和昨天的题目类似：如果 s[i] == s[j] 且 s[i+1:j-1] 是回文串，则 s[i:j] 也是回文串

然后，再利用动态规划计算最少分割次数。设 min[i] 为 s[0:i] 的最小分割次数：

• 如果 s[0:i] 本身是回文串，则 min[i] = 0，不需要分割

• 否则，枚举 j 作为最后一个分割点，如果 s[j+1:i] 是回文串，则 min[i] = min[j] + 1

最终返回 min[n-1]，即 s[0:n] 的最小分割次数

代码实现

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (boolean[] a : dp) {
            Arrays.fill(a, true);
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
        int[] min = new int[n];
        Arrays.fill(min, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            if (dp[0][i]) {
                min[i] = 0;
            } else {
                for (int j = 0; j < i; j++) {
                    if (dp[j + 1][i]) {
                        min[i] = Math.min(min[i], min[j] + 1);
                    }
                }
            }
        }
        return min[n - 1];
    }
}

复杂度分析

• 时间复杂度：

  • 预处理 dp[i][j] 需要遍历所有子串，复杂度为 O(n^2)

  • 计算 min[i] 也需要遍历所有可能的分割点，复杂度为 O(n^2)

  • 因此，总体时间复杂度为 O(n^2)

• 空间复杂度：

  • dp 数组存储所有子串的回文信息，占用 O(n^2) 空间

  • min 数组存储每个前缀的最小分割次数，占用 O(n) 空间

  • 总体空间复杂度为 O(n^2)

总结

本题通过两次动态规划解决问题，首先预处理回文子串信息，然后利用动态规划计算最少分割次数。相比昨天的题目，这道题不需要回溯，逻辑上更加简单，但同样展现了动态规划的强大应用。通过这道题，我进一步熟悉了如何使用 DP 解决字符串分割类问题

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。