专栏首页米扑专栏【leetcode】Palindrome Partitioning II

【leetcode】Palindrome Partitioning II

Question : 

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.

Anwser 1 :

class Solution {
public:
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() < 2)
            return 0;
        int length = s.size();
        int *minSegs = new int[length+1];
        minSegs[0] = 0;
        minSegs[1] = 1;
        int **dp = new int*[2];
        dp[0] = new int[length+2];
        dp[1] = new int[length+2];
        dp[0][0] = dp[1][0] = 0;
        dp[0][1] = dp[1][1] = 1;
        dp[0][2] = -1;
        
        int cur = 0;
        int pre = 1;
        for (int i=1; i<s.size(); i++) {
            int cur = i % 2;
            int pre = (i +1) % 2;
            minSegs[i+1] = minSegs[i] + 1;
            int n = 1;
            for (int j=0; dp[pre][j] != -1; j++) {
                int left = i-1-dp[pre][j];
                if (left>=0 && s[left]==s[i]) {
                    dp[cur][++n] = dp[pre][j] + 2;
                    if (minSegs[left] + 1 < minSegs[i+1])
                        minSegs[i+1] = minSegs[left] + 1;
                }
            }
            dp[cur][++n] = -1;
        }
        
        int min = minSegs[s.size()] - 1;
        delete []minSegs;
        return min;
    }
};

Anwser 2: :

class Solution {
public:
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		int len=s.length();
		int BIG=2*len;
		int num_line=len+1;
		vector<int> isPalindrome(num_line*num_line);
		for(int l=1;l<=len;l++)//两个木板之间有多少个字符
		{
			for (int i=0;i+l<num_line;i++)//从第0个木板开始,i+l为木板的序号
			{
				if (l==1)
				{
					isPalindrome[i*num_line+(i+l)]=1;
				}
				else if(l==2)
				{
					if (s[i]==s[i+l-1])
						isPalindrome[i*num_line+(i+l)]=1;
					else
						isPalindrome[i*num_line+(i+l)]=BIG;
				}
				else
				{
					if (s[i]==s[i+l-1])
						isPalindrome[i*num_line+(i+l)]=isPalindrome[(i+1)*num_line+(i+l-1)];
					else
						isPalindrome[i*num_line+(i+l)]=BIG;
				}
			}
		}
		vector<int> dist(num_line);
		vector<bool> labeled(num_line);
		for(int i=0;i<num_line;i++)
		{
			dist[i]=BIG;
			labeled[i]=false;
		}
		dist[0]=0;
		labeled[0]=true;
		int current_line=0;
		for(int i=1;i<num_line;i++)
		{	
			for(int d=current_line+1;d<num_line;d++)//对所有的相邻(在图中)的木板
			{
				if(!labeled[d])
				{
					if (dist[current_line]+isPalindrome[current_line*num_line+d]<dist[d])
					{
						dist[d]=dist[current_line]+isPalindrome[current_line*num_line+d];
					}
				}
			}
			int mindist=BIG;
			int minindex=-1;
			for(int i=0;i<num_line;i++)
			{
				if(!labeled[i])
				{
					if(mindist>dist[i])
					{
						minindex=i;
						mindist=dist[i];
					}
				}
			}
			current_line=minindex;
			labeled[minindex]=true;
		}

		return dist[num_line-1]-1;
	}
};

参考推荐:

leetcode:Palindrome Partitioning II

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Two Sum

    Given an array of integers, find two numbers such that they add up to a specific...

    阳光岛主
  • 【leetcode】Triangle

    Given a triangle, find the minimum path sum from top to bottom. Each step you ma...

    阳光岛主
  • 【leetcode】Longest Consecutive Sequence

    Given an unsorted array of integers, find the length of the longest consecutive ...

    阳光岛主
  • POJ 刷题系列:1083. Moving Tables

    POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

    用户1147447
  • hdu1025

    @坤的
  • HYSBZ 3676 回文串 (回文树)

    3676: [Apio2014]回文串 Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 1680  Solve...

    ShenduCC
  • 【每日算法Day 70】图解算法:小学生都会的数块数问题,你会吗?

    在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

    godweiyang
  • HDU4352 XHXJ's LIS(LIS 状压)

    刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

    attack
  • 一些零碎的小知识点

    小闫同学啊
  • BZOJ4299: Codechef FRBSUM(主席树)

    那么若$a[i + 1] > s_i + 1$,那么$a[i + 1]$不能被拼成

    attack

扫码关注云+社区

领取腾讯云代金券