>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

leetcode刷题 Palindrome Partitioning II

 

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.

__author__ = 'bone-lee'

class Solution:
    # @param s, a string
    # @return an integer
    def minCut(self, s):
        length=len(s)
        if length<2: return 0
        dp=[0]*(length+1)
        is_palindrome=[[False]*length for i in range(length)]
        for i in range(0,length+1):
            dp[i]=length-i-1
        for i in range(length-1,-1,-1):
            for j in range(i,length):
                if s[i]==s[j] and ((j-i)<=1 or is_palindrome[i+1][j-1]):
                    is_palindrome[i][j]=True
                    dp[i]=min(dp[j+1]+1,dp[i])
        return dp[0]

Meta

发布: 十二月 1, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 115

下一篇: leetcode刷题 Regular Expression Matching

上一篇: leetcode刷题 Jump Game II

Bookmark and Share

Tags

code leetcode python

comments powered by Disqus

返回顶部