代码随想录——分割回文串 II

题目

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

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

示例 1：

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

示例 2： 输入：s = “a” 输出：0

示例 3： 输入：s = “ab” 输出：1

提示：

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

思路

类似分割回文串，本题也可以用回溯，但是会超时，本题考虑动态规划

对于回文子串，两到基础题目一定要弄清楚：

1. 回文子串
2. 最长回文字串

动规五部曲：

1. 确定dp数组和下标含义
   dp[i]：范围是[0, i]的回文子串，最少分割次数是dp[i]

2. 确定递推公式
   如果要对长度为[0, i]的子串进行分割，分割点为j，分割后，根据dp[i]的定义，dp[j]就表示[0, j]区间的最小切割数量，此时如果区间[j + 1, i]是回文子串，那么dp[i] 就等于 dp[j] + 1，最后要找的是最少切割次数，所以递推公式为：
   dp[i] = min(dp[i], dp[j] + 1)

3. 初始化dp数组
   根据定义，dp[i]表示范围是[0, i]的回文子串，最少分割次数是dp[i]，那么dp[0]一定是0，因为长度为1的字符串最小分割次数就是0
   对于非零下标的dp[i]初始化，在递推公式dp[i] = min(dp[i], dp[j] + 1) 中可以看出每次要取最小的dp[i]，所以应该初始化为一个最大数，因为如果取0的话，会无法被覆盖，最终结果都是0

4. 确定遍历顺序
   根据递推公式：dp[i] = min(dp[i], dp[j] + 1)

j是在[0，i]之间，所以遍历i的for循环一定在外层，遍历j的for循环在内层

5. 举例推导dp数组
   以输入：“aabc” 为例：
   
   java代码如下：

class Solution {
	public int minCut(String s){
		if(s == null || s.length() == 0){
			return 0;
		}
		int len = s.length();
		
		//1、先判断是否是回文子串
		//isPalindromic记录子串[i..j]是否是回文串
		boolean[][] isPalindromic = new int[len][len];
		//从下到上:j —> j-1,从左到右:i —> i+1
		for(int i = len -1; i >= 0; i--){
			for(int j = i;j < len; j++){
				if(s.charAt(i) == s.charAt(j)){//两端相等的话
					if(j - i <= 2){
						isPalindromic[i][j] = true;
					} else {//长度相差大于2则收缩
						isPalindromic[i][j] = isPalindromic[i + 1][j - 1];
					}
				} else {//两端不相等的话
					isPalindromic[i][j] = false;
				}
			}
		}
		//2、判断最小分割次数
		//dp[i] 表示[0..i]的最小分割次数
		int[] dp = new dp[len];
		for(int i = 0; i < len; i++){
			//初始考虑最坏的情况。 1个字符分割0次， len个字符分割 len - 1次,这样就可以保证，便利的过程中一定可以被覆盖更新
			dp[i] = i;
		}
		
		for(int i = 1; i < len; i++){
			if(isPalindromic[0][i]){
				// 表示s[0..i]是回文了，那 dp[i] = 0, 一次也不用分割
				dp[i] = 0;
				continue;
			}
			for(int j = 0; j < i; j++){//j为分割点,比如[0,i]被j分为[0,j]和[j+1,i]，那么[1,j]最少分割次数为dp[j],只需要判断[j+1,i]是否是回文子串即可,如果是的话,则dp[i] = dp[j] + 1
				if(isPalindromic[j + 1][i]){//如果[j+1,i]是回文子串
					dp[i] = Math.min(dp[i],dp[j] + 1);//取最小值
				}			
			}
		}
		return dp[len - 1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47