132 分割回文串II

题目

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

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

示例 1：

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

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

输入：s = “ab”
输出：1

• 动态规划

class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        vector<int> f(n,INT_MAX);//f[i]表示区间[0,i]的回文串最小分割次数
        vector<vector<bool>> p(n,vector<bool>(n,false));//p[i,j]表示区间[i,j]的字符串是否为回文串

		//判断回文串
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j]&&(j-i<2||p[i+1][j-1]==true))
                {
                    p[i][j]=true;
                }
            }
        }
        //记录字符区间[0,r]的回文串最小分割次数
        for(int r=0;r<n;r++)
        {
            if(p[0][r]==true) f[r]=0;//如果[0,r]就是回文串，则不需要分割
            else{//否则
                f[r]=r;//最大分割次数为r，即把当前区间内的元素一个一分
                //寻找当前区间的最小分割次数
                //如果[l,r]是回文串，则分割次数为f[l-1]+1,即[0,l-1]区间的最小分割次数加上在l处的一个切割
                //尝试所有的l可能位置，找到f[r]的最小值
                for(int l=1;l<=r;l++)
                {
                    if(p[l][r]) f[r]=min(f[r],f[l-1]+1);
                }
            }
        }
        return f[n-1];//返回f[n-1]表示区间[0,n]的最小分割次数
    }
};
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

• 空间复杂度O(n^2)
• 时间复杂度O(n^2)
• 思路
  • 采用一个二维数组p[i][j]记录s[i][j]是否为回文串
    • 状态转移方程：p[i][j]= s[i]==s[j] && (j-1<1||p[i+1][j-1])
    • 当前i和j所指的元素相同，且当前区间去掉这两个元素的字符串也相同或者当前区间只有两个元素
    • 如果想去掉判断条件j-i<1，可以初始将dp数组置为true，在填dp数组时碰到无意义的ij组合也不会导致结果出错，此时需要将判断true改为判断并确定false
  • 采用一个一维数组f[i]记录区间[0,i]的最小回文切割次数
    • 状态转移方程：f[r]=min{f[l]+1}, 0
    • 如果字符串[l,r]为回文串，则一种可能的切割次数就是f[l-1]+1，加1表示在l处切割一次。尝试l的所有可能位置，求f[r]的最小值