首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 132 Palindrome Partitioning II

Leetcode 132 Palindrome Partitioning II

作者头像
triplebee
发布2018-01-12 14:52:15
5630
发布2018-01-12 14:52:15
举报

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

承接上一题,求回文串分割的最小步数。

因为不用求出所有分割,所以很显然是DP。

我第一想法是用dp[i]表示分割到这一位的最小步数,转移为:

dp[i] = 0 ,开始到这里为回文

dp[i] = min(dp[i], dp[j-1]+1), 遍历前面每一位,找到从他之后到i是回文串的,求出dp[j-1]+1的最小值

然而超时了,再分析,从前往后必须把所有情况都遍历才能得到最后一位,如果反过来,只求想知道的子情况,求出最小就停止呢?

没超,不过很慢,那他们都是怎么过的呢?

原来是优化了判断回文串的部分,去掉了很多重复判断的部分,直接用二维数组表示两位之间的串是不是回文串

在discuss中又看到更好的解法,在枚举回文串的过程中DP,相当于省掉了枚举子情况的一层循环。

先贴超时的,再贴优美解!

class Solution {
public:
    bool judge(string s)  
    {  
        for(int i=0;i<s.size()/2;i++) if(s[i] != s[s.size()-1-i]) return false;  
        return true;  
    }  
    int minCut(string s) {
        vector<int> dp(s.size(),s.size());
        for(int i=0;i<s.size();i++)
        {
            if(judge(s.substr(0,i+1))) 
            {
                dp[i] = 0;
                continue;
            }
            for(int j=1;j<=i;j++) if(judge(s.substr(j,i-j+1))) dp[i] = min(dp[i], dp[j-1]+1);
        }
        return dp[s.size()-1];
    }
};

思路和代码都很优美!

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> cut(n+1, 0);  
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);
            for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
        }
        return cut[n];
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-10-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档