当前位置：首页 > news >正文

LCR 094. 分割回文串 II

news 2025/6/2 7:49:51

直达链接：LCR 094. 分割回文串 II

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

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

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

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

解题思路：使用动态规划

首先使用一个二维数组 isPalindrome 来记录字符串 s 的子串 s[i...j] 是否是回文。这样可以快速查询任意子串是否为回文。
使用另一个动态规划数组 dp，其中 dp[i] 表示子串 s[0...i-1] 的最小分割次数。初始化时，dp[i] 的最大值为 i-1（即每个字符都分割一次）。然后遍历字符串，对于每个位置 i，检查所有可能的 j（从 0 到 i），如果 s[j...i] 是回文，那么 dp[i+1] 可以更新为 min(dp[i+1], dp[j] + 1)。

class Solution {public int minCut(String s) {int n = s.length();boolean[][] isPalindrome = new boolean[n][n];int[] dp = new int[n];for (int i = 0; i < n; i++) {isPalindrome[i][i] = true;}for (int i = 0; i < n - 1; i++) {if (s.charAt(i) == s.charAt(i + 1)) {isPalindrome[i][i + 1] = true;}}for (int len = 3; len <= n; len++) {for (int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;if (s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1]) {isPalindrome[i][j] = true;}}}for (int i = 0; i < n; i++) {if (isPalindrome[0][i]) {dp[i] = 0;} else {dp[i] = i;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];}
}

注释版：

class Solution {public int minCut(String s) {int n = s.length();// isPalindrome[i][j] 表示子串 s[i...j] 是否是回文boolean[][] isPalindrome = new boolean[n][n];// dp[i] 表示子串 s[0...i] 的最小分割次数int[] dp = new int[n];// 初始化长度为1的子串，单个字符肯定是回文for (int i = 0; i < n; i++) {isPalindrome[i][i] = true;}// 初始化长度为2的子串，检查两个字符是否相同for (int i = 0; i < n - 1; i++) {if (s.charAt(i) == s.charAt(i + 1)) {isPalindrome[i][i + 1] = true;}}// 处理长度大于2的子串，检查首尾字符是否相同且中间子串是否为回文for (int len = 3; len <= n; len++) {for (int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;if (s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1]) {isPalindrome[i][j] = true;}}}// 计算最小分割次数for (int i = 0; i < n; i++) {// 如果子串 s[0...i] 本身就是回文，无需分割if (isPalindrome[0][i]) {dp[i] = 0;} else {// 初始化为最大可能分割次数，即每个字符都分割一次dp[i] = i;// 遍历所有可能的分割点 jfor (int j = 0; j < i; j++) {// 如果子串 s[j+1...i] 是回文，则更新 dp[i]if (isPalindrome[j + 1][i]) {dp[i] = Math.min(dp[i], dp[j] + 1);}}}}// 返回整个字符串的最小分割次数return dp[n - 1];}
}