【算法挨揍日记】day35——1745. 分割回文串 IV、132. 分割回文串 II

落日映苍穹つ 2024-02-17 13:01 37阅读 0赞

## 1745. 分割回文串 IV ##

[1745. 分割回文串 IV][1745. _ IV]

### 题目描述： ###

给你一个字符串 `s` ，如果可以将它分割成三个 **非空** 回文子字符串，那么返回 `true` ，否则返回 `false` 。

当一个字符串正着读和反着读是一模一样的，就称其为 **回文字符串** 。

![be11465052ad437a9c7d62945484d1f4.png][]

### 解题思路： ###

在647题的基础上， 我们从后向前遍历dp表中所有为true的情况，看否可以将他们分为3段

### 解题代码： ###

class Solution {
    public:
        bool checkPartitioning(string s) {
            int n=s.size();
            vector<vector<bool>>dp(n,vector(n,false));
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i;j<n;j++)
                {
                    if(s[i]==s[j])
                    {
                        if(i==j)dp[i][j]=true;
                        else if(i+1==j)dp[i][j]=true;
                        else dp[i][j]=dp[i+1][j-1];
                    }
                }
            }
           for(int i=n-1;i>=0;i--)
           {
               if(dp[i][n-1]==true)
               {
                   for(int begin=i-1;begin>0;begin--)
                   {
                       if(dp[begin][i-1]==true&&dp[0][begin-1]==true)
                       return true;
                   }
               }
           }
           return false;
    
        }
    };

## 132. 分割回文串 II ##

[132. 分割回文串 II][132. _ II]

### 题目描述： ###

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

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

![be7c251ad06341c5ac0361acd41be8ae.png][]

### 解题思路：    ###

算法思路：

1.  状态表⽰：

根据「经验」，继续尝试⽤  i  位置为结尾，定义状态表⽰，看看能否解决问题：

dp\[i\]  表⽰：  s  中  \[0, i\]  区间上的字符串，最少分割的次数。

2.  状态转移⽅程：

状态转移⽅程⼀般都是根据「最后⼀个位置」的信息来分析：设  0 <= j <= i  ，那么我们可以

根据  j ~ i  位置上的⼦串是否是回⽂串分成下⾯两类：

i.  当  \[j ,i\]  位置上的⼦串能够构成⼀个回⽂串，那么  dp\[i\]  就等于  \[0, j - 1\]  区

间上最少回⽂串的个数 + 1，即  dp\[i\] = dp\[j - 1\] + 1  ；

ii.  当  \[j ,i\]  位置上的⼦串不能构成⼀个回⽂串，此时  j  位置就不⽤考虑。

由于我们要的是最⼩值，因此应该循环遍历⼀遍  j  的取值，拿到⾥⾯的最⼩值即可。

优化：我们在状态转移⽅程⾥⾯分析到，要能够快速判读字符串⾥⾯的⼦串是否回⽂。因此，我们

可以先处理⼀个  dp  表，⾥⾯保存所有⼦串是否回⽂的信息。

3.  初始化：

观察「状态转移⽅程」，我们会⽤到  j - 1  位置的值。我们可以思考⼀下当  j == 0  的时候，

表⽰的区间就是  \[0, i\]  。如果  \[0, i\]  区间上的字符串已经是回⽂串了，最⼩的回⽂串就是

1  了，  j  往后的值就不⽤遍历了。

因此，我们可以在循环遍历  j  的值之前处理  j == 0  的情况，然后  j  从  1  开始循环。

但是，为了防⽌求  min  操作时，  0  ⼲扰结果。我们先把表⾥⾯的值初始化为「⽆穷⼤」。

4.  填表顺序：

毫⽆疑问是「从左往右」。

5.  返回值：

根据「状态表⽰」，应该返回  dp\[n - 1\]  。

### 解题代码： ###

class Solution {
    public:
        int minCut(string s) {
            int n=s.size();
            vector<vector<bool>>dp(n,vector(n,false));
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i;j<n;j++)
                {
                    if(s[i]==s[j])
                    {
                        if(i==j)dp[i][j]=true;
                        else if(i+1==j)dp[i][j]=true;
                        else dp[i][j]=dp[i+1][j-1];
                    }
                }
            }
    
           vector<int>f(n,INT_MAX);
           for(int i=0;i<n;i++)
           {
               if(dp[0][i]==true)
               f[i]=0;
               else
               {
                   for(int j=i;j>0;j--)
                   {
                       if(dp[j][i]==true)
                        f[i]=min(f[i],f[j-1]+1);
                   }
               }
           }
            return f[n-1];
        }
    };

[1745. _ IV]: https://leetcode.cn/problems/palindrome-partitioning-iv/
[be11465052ad437a9c7d62945484d1f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/c040d584e26544289f8e0373fccde7a2.png
[132. _ II]: https://leetcode.cn/problems/palindrome-partitioning-ii/
[be7c251ad06341c5ac0361acd41be8ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/1c999c92e80741939ebbf65fa1b8d872.png