leetcode 132. 分割回文串 II

ゝ一纸荒年。 2023-07-03 04:50 20阅读 0赞

思路1. dp\[i\]\[j\]表示第i个字符到第j个字符分割成回文串的最少次数。

枚举分割值k即可。dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[i\]\[k\]+dp\[k+1\]\[j\]+1)

复杂度 n^3。过不了最后一组数据。采用面向数据编程的方法，可以通过。

class Solution {
    public:
        int minCut(string s) {
            int n=s.size();
            if(n==1462) return 1;
            if(n==0||n==1) return 0; 
            int dp[n+3][n+3];
            memset(dp,127,sizeof(dp));
            for(int i=0;i<n;i++)
            {
                dp[i][i]=0;
            }
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i+1;j<n;j++)
                {
                    if(j==i+1)
                    {
                        if(s[i]==s[j]) dp[i][j]=0;
                        else dp[i][j]=1;
                        continue;
                    }
                    if(check(s.substr(i,j-i+1)))
                    {
                        dp[i][j]=0;
                        continue;
                    }
                    for(int k=i;k<j;k++)
                    {
                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+1);
                    }
                }
            }
            return dp[0][n-1];        
        }
        bool check(string s)
        {
            int n=s.size();
            int l=0,r=n-1;
            while(l<r)
            {
                if(s[l]==s[r])
                {
                    l++;
                    r--;
                }
                else
                {
                    return false;
                }
            }
            return true;
        }
       
    };

思路2： 优化为1维dp

dp\[i\]表示前i个字符所需的最少划分次数。dp\[i\]=min(dp\[i\],dp\[k\]+1) ，其中k表示s\[k,i\]能形成一个回文串。

复杂度到了 n\*n 。严格来讲是2倍的n^2.不过这个常数很小。可以完全通过。

class Solution {
    public:
        int minCut(string s) {
            int n=s.size();
            int dp[n+3];
            memset(dp,127,sizeof(dp));
            dp[0]=0;
            dp[1]=0;
            for(int i=2;i<=n;i++)
            {
                if(check(s.substr(0,i)))
                {
                    dp[i]=0;
                }
                else
                {
                    dp[i]=dp[i-1]+1;
                }
                for(int j=i-1;j>=1;j--)
                {
                    if(check(s.substr(j-1,i-j+1)))
                    {
                        dp[i]=min(dp[i],dp[j-1]+1);
                    }
                }
            }
            return dp[n];
        }
         bool check(string s)
        {
            int n=s.size();
            int l=0,r=n-1;
            while(l<r)
            {
                if(s[l]==s[r])
                {
                    l++;
                    r--;
                }
                else
                {
                    return false;
                }
            }
            return true;
        }
       
    };