回文串问题

目录

回文子串

解法一【中心扩散法】

解法二【动态规划法】

最长回文子串

分割回文串IV

分割回文串II

最长回文子序列

让字符串成为回文串的最少插入次数

---

声明：下面的讲解，主要采用动态规划法来解决！！！ 

回文子串

题目

思路

判断一个字符串是否是回文的，我们很容易想到中心扩散法，从字符串中间向两端扩散或者两头向中间收拢，还可以采用动态规划来解决，下面将介绍两种方法来解决这道题。

解法一【中心扩散法】

通过穷举所有可能的情况，并判断该字符串是否是回文串。

代码

class Solution {
public:
    int sum=0;
 
    int countSubstrings(string s) {
        helper(s,0);
        return sum;
    }
    void helper(string s,int start){
        if(start==s.size()) return;
        for(int i=start;isize();i++){
            if(isPalindrome(s,start,i)){
                sum++;
            }
        }
        helper(s,start+1);
    }
 
    bool isPalindrome(string s,int l,int r){
        while(l
            if(s[l++]!=s[r--])
                return false;
        }
        return true;
    }
};

解法二【动态规划法】

状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。

状态转移方程：

初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。

填表顺序：从下往上。

我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。

代码

class Solution {
public:
    int sum=0;
 
    int countSubstrings(string s) {
        int n=s.size();
        vectorbool>> dp(n,vector<bool>(n));
        //dp[i][j]=dp[i+1][j-1]
        for(int i=n-1;i>=0;i--)
            for(int j=n-1;j>=i;j--){
                if(s[i]!=s[j]) dp[i][j]=false;
                else{
                    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=0;i
            for(int j=i;j
                if(dp[i][j]) sum++;
        return sum;
    }
};

最长回文子串

题目

思路

和上一道题一样，我们需要穷举出该字符串所有子串的情况，并判断是否是回文串，而且需要记录是回文串的起始位置和长度，便于找出最长回文子串，如果采用中心扩散法，时间复杂度是O(N^3)，可能会超时，但经过我尝试，这种方法的确会超时。所以下面我们采用动态规划，穷举出该字符串所有子串的情况，并判断是否是回文串，时间复杂度是O(N^2)，不会超时。

解法

状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。

状态转移方程：

初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。

填表顺序：从下往上。

我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。

代码

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        vectorbool>> dp(n,vector<bool>(n));
        //dp[i][j]=dp[i+1][j-1]
        for(int i=n-1;i>=0;i--)
            for(int j=n-1;j>=i;j--){
                if(s[i]!=s[j]) dp[i][j]=false;
                else{
                    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];
                }
            }
        int len=1,pos=0;
        for(int i=0;i
            for(int j=i;j
                if(dp[i][j] && j-i+1>len){
                    len=j-i+1;
                    pos=i;
                }
        return s.substr(pos,len);
    }
};

分割回文串IV

题目

思路

其实解法就是我们找到两个位置，将字符串分割为三段区间，并且满足三段区间都是回文串即可，如果采用中心扩散法，分析可知时间复杂度是O(N^3)，可能会超时，所以接下来，我们依旧采用一种算是“一劳永逸”的解法，动态规划，我们会觉得这道题不是困难题了，而是so easy。

解法

状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。

状态转移方程：

初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。

填表顺序：从下往上。

我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。

代码

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

分割回文串II

题目

思路

我们可以尝试以某个位置为结尾，并判断[0,i]区间是否是回文串，如果是的话，这段区间的最少分割次数就是0，如果不是的话，需要分情况讨论。

先声明一点，下面我依旧先使用动态规划穷举出所有可能的子字符串，下一步还会使用动态规划，这样的话，就会两使用dp来表示，肯定是不可以的，但是基于前一步的动态规划在前几道题已经讲过，所以这里就不再重新画图了，把前面的图拿过来直接使用了！！！！

状态表示：dp[i][j]表示字符串[i,j]区间的子字符串是否是回文串。

状态转移方程：

初始化：根据状态转移方程推知，由于我们已经加了限制条件，所以不用初始化。

填表顺序：从下往上。

我们只需要填写红色区域的值就可以了，最终会得到字符串所有子字符串是否是回文串的结果，这样只需要遍历图中红色区域，就可以知道这个字符串中有多少个回文子字符串了。

填表顺序：从下往上。

状态表示：dp[i]表示以i位置为结尾，使[0,i]区间的字符串成为回文子串的最少分割次数。

填表顺序：从左往右。

代码

class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        vectorbool>> isP(n,vector<bool>(n));
        //dp[i][j]=dp[i+1][j-1]
        for(int i=n-1;i>=0;i--)
            for(int j=i;j
                if(s[i]==s[j])
                    isP[i][j]=i+11][j-1]:true;
            }
        vector<int> dp(n,0x3f3f3f3f);
        //dp[i] 表示从0到i最少分割次数
        for(int i=0;i
        {
            if(isP[0][i]) dp[i]=0;
            else{
                for(int j=i;j>0;j--)
                    if(isP[j][i]) dp[i]=min(dp[j-1]+1,dp[i]);
            }
        }
        return dp[n-1];
    }
};

最长回文子序列

题目

思路

如果我们依旧采用以某个位置为结尾来分析问题，会发现推不出状态转移方程，下面尝试采用以某一段区间来进行分析本题。

状态表示：dp[i,j]表示[i,j]区间内最长的回文子序列长度。

状态转移方程：

填表顺序：从下往上，从左往右。

代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vectorint>> dp(n,vector<int>(n));
        //dp[i][j] 表示[i,j]区间最长回文子序列长度
        for(int i=n-1;i>=0;i--)
        {
            dp[i][i]=1;
            for(int j=i+1;j
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
            }
        }
        return dp[0][n-1];
    }
};

让字符串成为回文串的最少插入次数

题目

思路

如果我们依旧采用以某个位置为结尾来分析问题，会发现推不出状态转移方程，下面我们尝试采用以某一段区间来进行分析本题。

状态表示：dp[i,j]表示让[i,j]区间字符串成为回文串的最少插入次数。

状态转移方程：

填表顺序：从下往上，从左往右。

代码

class Solution {
public:
    int minInsertions(string s) {
        int n=s.size();
        vectorint>> dp(n,vector<int>(n));
        //dp[i][j]表示[i,j]区间称为回文串的最少插入次数
        for(int i=n-1;i>=0;i--){
            dp[i][i]=0;
            for(int j=i+1;j
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
                else dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;
            }
        }
        return dp[0][n-1];
    }
};