分割回文串

LeetCode 131

题目连接

分割回文串I

思路分析：

这道题直接暴力枚举+回溯，是一道模板题(考试的时候脑子短路了），可以先用dp思路预处理关于回文子串的判定

代码：

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<bool>> f;
    vector<vector<string>> partition(string s) {
      int n=s.size();
      f=vector<vector<bool>>(n,vector<bool>(n,0));
      //预处理
      for(int j=0;j<n;j++){
          for(int i=0;i<=j;i++){
              if(i==j) f[i][j]=true;
              else{
                  if(s[i]==s[j]){
                      if(i+1>j-1||f[i+1][j-1]) f[i][j]=true;
                  }
              }
          }
      }
      dfs(s,0);
      return res;
    }
    void dfs(string &s,int u){
        if(u==s.size()){
            res.push_back(path);
            return;
        }
       //枚举当前位置可能的回文子串
        for(int i=u;i<s.size();i++){
            if(f[u][i]){
                path.push_back(s.substr(u,i-u+1));
                dfs(s,i+1);
                path.pop_back();
            }
        }
    }
};

LeetCode 132

题目连接

分割回文串2

思路分析：

DP：f[i]表示以1-i的串中需要的最小分割次数，这里状态转移的判断是依据最后一个回文子串的不同来划分的，所以状态转移为：
f[i]=min(f[i],f[i-p]+1),且s[i-p+1]到s[i]之间为回文串

代码展示：

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

分割回文串

原文：https://www.cnblogs.com/taoger/p/14017024.html