一、回文子串

 该题有3种解法

（1）中心扩展算法（在字符串章节有介绍）时间复杂度O（N^2）,空间复杂度O（1）

（2）马丁车算法（专门用来解决回文串问题，但是适用返回太窄）时间复杂度O（N）,空间复杂度O（N）

（3）动态规划（可以将所有回文信息都保存在dp表中）时间复杂度O（N^2）,空间复杂度O（N^2）

这边重点介绍动态规划的做法。

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]的子串是否是回文串（i<=j）只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

dp表中true的个数

class Solution {
public:
    int countSubstrings(string s) {
      //动态规划的做法
      int ret=0;
      //s[i]==s[j]  1、i==j  2、i+1==j  3、dp[i+1][j-1]?
      int n=s.size();
      vector<vector<bool>> dp(n,vector<bool>(n));
      //只要右上半区 
      for(int i=n-1;i>=0;--i)  //要从下往上  左右无所谓，因为用不到
        for(int j=i;j<n;++j) //只要右上半区
            if(s[i]==s[j]) ret+=dp[i][j]=i+1<j?dp[i+1][j-1]:true;
      return ret;
    }
};

中心拓展算法：

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        int ret=0;
        for(int i=0;i<2*n-1;++i){
           int l=i/2,r=i/2+i%2;
           while(l>=0&&r<n&&s[l]==s[r]) {
            --l;
            ++r;
            ++ret;
           }
        }
        return ret;
    }
};

 二、最长回文子串

 

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]的子串是否是回文串（i<=j）只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

dp表中为true以及长度最大的子串的起始位置和长度

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

三、分割回文子串I

解法1：动归预处理+回溯

class Solution {
public:
   //动归预处理+回溯
    vector<vector<bool>> dp;//dp预处理
    vector<vector<string>> ret;//记录返回的结果
    vector<string> path;//记录路径的结果
    int n;
    vector<vector<string>> partition(string s) {
       //dp预处理
       n=s.size();
       dp.resize(n,vector<bool>(n));
       for(int i=n-1;i>=0;--i)
          for(int j=i;j<n;++j)
            if(s[i]==s[j])  dp[i][j]=i+1<j?dp[i+1][j-1]:true;
        //将dp数组交给dfs去处理
        dfs(s,0);
        return ret;
    }
    void dfs(string&s,int i)
    {
        if(i==n) 
        {
            ret.push_back(path);
            return;
        }
        for(int j=i;j<n;++j)
            if(dp[i][j])
            {
                path.emplace_back(s.substr(i,j-i+1));
                dfs(s,j+1);
                path.pop_back();
            }
    }
};

 解法2：回溯+记忆化搜索

class Solution {
public:
//回溯+记忆化搜索
    vector<vector<int>> f;//记忆化数组  0表示未搜索，1表示回文，-1表示不回文
    vector<vector<string>> ret;//记录返回的结果
    vector<string> path;//记录路径的结果
    int n;
    vector<vector<string>> partition(string s) {
      n=s.size();
      f.resize(n,vector<int>(n));
      //交给dfs帮助我们解决
      dfs(s,0);
      return ret;
    }
    void dfs(const string&s,int i)
    {
        if(i==n) 
        {
            ret.emplace_back(path);
            return;
        }
        for(int j=i;j<n;++j)
          if(ispal(s,i,j))
        {
            path.emplace_back(s.substr(i,j-i+1));
            dfs(s,j+1);
            path.pop_back();
        }
    }
    bool ispal(const string&s,int i,int j) //判断i->j是否回文
    {
       //先看看备忘录
       if(f[i][j]) return f[i][j];
       if(s[i]!=s[j]) return f[i][j]=false;
       else return f[i][j]=i+1<j?ispal(s,i+1,j-1):true;
    }
};

四、分割回文子串II

算法原理：

1、状态表示（经验+题目要求）

dp[i]表示s字符串[0，i]区间上的最长子串的最小分割次数

 2、状态转移方程

dp[i]:  

(1)0-i回文——>0

(2)0-i不是回文——>j-i是否回文——>min(dp[i],dp[j-1]+1)

3、初始化

都初始化为整型最大值，否则最后dp表里都是0会影响结果

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

dp[n-1]

class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        vector<vector<bool>> ispal(n,vector<bool>(n));
        for(int i=n-1;i>=0;--i)
          for(int j=i;j<n;++j)
            if(s[i]==s[j]) ispal[i][j]=i+1<j?ispal[i+1][j-1]:true;
        
        //dp[i]表示以i位置为结尾时分割成子串所需要的最少分割次数
        vector<int> dp(n,INT_MAX);
        for(int i=0;i<n;++i){ //去看看左边要怎么切割
          if(ispal[0][i]) dp[i]=0;
          for(int j=1;j<=i;++j)
            if(ispal[j][i]) dp[i]=min(dp[i],dp[j-1]+1);
        }
        return dp[n-1];
    }
};

五、分割回文子串III（经典）

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示对于字符串的前i个字符，将他分割成j个子串，所需修改的最少字符数

 2、状态转移方程

int cost(string&s,int l,int r) 表示从s的i-j位置，变成回文串所需要的最小修改次数

dp[i][j]:  

(1)j==1（没有分割）  cost（s,0,i-1）

(2)j>1——>min(dp[i][j],dp[m][j-1]+cost(s,m,i-1))

3、初始化

初始化成INT_MAX 确保不影响最终结果 dp[0][0]=0 确保不影响结果

4、填表顺序

上到下，左到右

5、返回值

dp[n][k]

回溯预处理：

class Solution {
public:
    int palindromePartition(string s, int k) {
      //ispal[i][j]预处理  i-j修改几个字符可以将他变成回文串 
      //s[i]==s[j] i+1<j? ispal[i+1][j-1]       
      //s[i]!=s[j] i+1<j? ispal[i+1][j-1]+1
      int n=s.size();
      //dp[i][j]表示以i位置为结尾时分割成k个子串  所需要修改的最少字符数 //0表示空串 有意义
      vector<vector<int>> dp(n+1, vector<int>(k+1,0x3f3f3f3f));
      dp[0][0]=0;
      for(int i=1;i<=n;++i)
        for(int j=1;j<=min(k,i);++j)  //dp[i][j]=min(dp[i][j],dp[k][j-1]+topal[k][i-1])
          for(int t=j-1;t<i;++t)
            dp[i][j]=min(dp[i][j],dp[t][j-1]+cost(s,t,i-1));
      return dp[n][k];
    }
    int cost(string& s, int l, int r) {
        int ret = 0;
        for (int i = l, j = r; i < j; ++i, --j) 
            if (s[i] != s[j]) ++ret;
        return ret;
    }
};

动归预处理： 

class Solution {
public:
    int palindromePartition(string s, int k) {
      //ispal[i][j]预处理  i-j修改几个字符可以将他变成回文串 
      //s[i]==s[j] i+1<j? ispal[i+1][j-1]       
      //s[i]!=s[j] i+1<j? ispal[i+1][j-1]+1
      int n=s.size();
      vector<vector<int>> topal(n,vector<int>(n));
      for(int i=n-1;i>=0;--i)
        for(int j=i+1;j<n;++j)
          topal[i][j]= topal[i+1][j-1]+(s[i]==s[j]?0:1);
      //dp[i][j]表示以i位置为结尾时分割成k个子串  所需要修改的最少字符数 //0表示空串 有意义
      vector<vector<int>> dp(n+1, vector<int>(k+1,0x3f3f3f3f));
      dp[0][0]=0;
      for(int i=1;i<=n;++i)
        for(int j=1;j<=min(k,i);++j)  //dp[i][j]=min(dp[i][j],dp[k][j-1]+topal[k][i-1])
          for(int t=j-1;t<i;++t)
            dp[i][j]=min(dp[i][j],dp[t][j-1]+topal[t][i-1]);
      return dp[n][k];
    }
};

六、分割回文串IV

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]的子串是否是回文串（i<=j）只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1]，所以必须要从下往上填 ， 左右顺序不重要

5、返回值

第二次枚举，先固定第一个位置，然后固定第二个位置，看看由两个位置分割出来的三个区域是否都为true

class Solution {
public:
    bool checkPartitioning(string s) {
        int n=s.size();
        vector<vector<bool>> ispal(n,vector<bool>(n));
        for(int i=n-1;i>=0;--i)
          for(int j=i;j<n;++j)
            if(s[i]==s[j]) ispal[i][j]=i+1<j?ispal[i+1][j-1]:true;
        //开始枚举 看看是否存在三个位置都是true的！！
        for(int i=1;i<n-1;++i)
          for(int j=i;j<n-1;++j)
            if(ispal[0][i-1]&&ispal[i][j]&&ispal[j+1][n-1]) return true;
        return false;
    }
};

七、不重叠回文子字符串的最大数目

中心拓展 +dp：

class Solution {
public:
    int maxPalindromes(string s, int k) {
        //dp[i]表示0->i中的不重叠回文子字符串的最大数目
        int n=s.size();
        vector<int> dp(n+1);
        //如果s[i]不在回文串中 dp[i+1]=dp[i]
        //如果s[r]在回文串中，采用中心扩展，l->r是回文子串，且r-l+1>=k 有dp[i]=max(dp[i],dp[l-1]+1)
        for(int i=0;i<n*2-1;++i)
        {
            //两边到中间不适合判断长度，应该从中间到两边
          int l=i/2,r=l+i%2; //中心扩展判断是否回文
          dp[l+1]=max(dp[l],dp[l+1]);
          for(;l>=0&&r<n&&s[l]==s[r];--l,++r)
             if(r-l+1>=k)
             {
                dp[r+1]=max(dp[r+1],dp[l]+1);
                break;
             }
        }
        return dp[n];
    }
};

预处理+dp

class Solution {
public:
    int maxPalindromes(string s, int k) {
        //预处理
        int n=s.size();
        if(k==1) return n;
        vector<vector<bool>> ispal(n,vector<bool>(n));
        for(int i=n-1;i>=0;--i)
          for(int j=i;j<n;++j)
            if(s[i]==s[j]) ispal[i][j]=i+1<j?ispal[i+1][j-1]:true;
        //dp[n]表示0-n能选择的子字符串的最大数目
       vector<int> f(n+1);
        for(int i=k;i<=n;++i) {
            f[i] = f[i-1];
            //只要j <= i-k-1, 那么如果[j,i]是回文，则[j+1, i-1] 长度为i-j-1>=k 并且是回文
            //这是[0~i-1]的子问题，所以f[j] + 1 <= f[i]
            for(int j = i-k;j>=max(i-k-1,0);--j) {
                f[i] = max(f[j] + ispal[j][i-1], f[i]);
            }
        }
        return f[n];
    }
};

 

八、最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) 
    {
       //子序列和子串的区别就是可以不连续
       int n=s.size();
       vector<vector<int>> dp(n,vector<int>(n));//只会用到右上半部分
       for(int i=n-1;i>=0;--i)
       {
        //dp[i][j]表示i-j区间内所有子序列中，最长回文子序列的长度
          dp[i][i]=1;
          for(int j=i+1;j<n;++j)
            if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2; //i+1=j的情况可以不用考虑 
            //虽然会出现用不到的格子，但是里面是0所以不会影响计算结果
            else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
       }
       return dp[0][n-1];
    }
};

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]所有子序列中的最长子序列的长度

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>max(dp[i,j-1],dp[i+1][j])

(2)s[i]==s[j]——>

      i==j  1

      i+1==j   2

      dp[i+1][j-1]+2

3、初始化

初始化为0  dp[i][i]=1

4、填表顺序

上到下，左到右

5、返回值

dp[0][n-1]

九、让字符串成为回文串的最小插入次数

 

算法原理：

1、状态表示（经验+题目要求）

dp[i][j]表示s字符串[i,j]子串，使他成为回文子串的最小插入次数

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>min(dp[i,j-1],dp[i+1][j])+1

(2)s[i]==s[j]——>

      i==j  0

      i+1==j   0

      dp[i+1][j-1]

3、初始化

初始化为0 

4、填表顺序

下往上，左到右

5、返回值

dp[0][n-1]

class Solution {
public:
    int minInsertions(string s) {
       int n=s.size();
       vector<vector<int>> dp(n,vector<int>(n));
       for(int i=n-1;i>=0;--i)
         for(int j=i+1;j<n;++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];
    }
};