[LeetCode]题解（python）：132-Palindrome Partitioning II

题目来源：

　　https://leetcode.com/problems/palindrome-partitioning-ii/

题意分析：

　　给定一个s，可以将s拆成若干个回文子字符串之和，如果拆成了m个子字符串，那么我们称s可以被m-1 cut。那么返回s的最小cut。

题目思路：

　　这是一个动态规划问题。这里需要二重动态规划，一个用来记录p[i][j]判断s[i][j]是否回文字符串，另外一个ans[i]代表s[:i]的最小cut是多少。如果s[i :j]是回文字符串，那么ans[j] = min(ans[j],ans[i - 1] + 1)。

代码（python）：

 class Solution(object):

     def minCut(self, s):

         """

         :type s: str

         :rtype: int

         """

         size = len(s)

         ans = [i for i in range(size)]

         p = [[False for i in range(size)] for j in range(size)]

         j = 1

         while j < size:

             i,ans[j] = j - 1,min(ans[j],ans[j - 1] + 1)

             p[j][j] = True

             while i >= 0:

                 if s[i] == s[j] and ((j - i) < 2 or  p[i+1][j-1]):

                     p[i][j] = True

                     if i == 0:

                         ans[j] = 0

                     else:

                         ans[j] = min(ans[j],ans[i - 1] + 1)

                 i -= 1

             j += 1

         return ans[size - 1]

巴特西

[LeetCode]题解（python）：132-Palindrome Partitioning II

最新文章

热门文章