郑州网站优化方案/易推客app拉新平台

108. 分割回文串 II

给定一个字符串s，将s分割成一些子串，使每个子串都是回文。

返回s符合要求的的最少分割次数。

样例

比如，给出字符串s = "aab"，

返回 1， 因为进行一次分割可以将字符串s分割成["aa","b"]这样两个回文子串

解题思路：

class Solution:"""@param s: A string@return: An integer"""def minCut(self, s):# write your code herePalin = self.isPalindrom(s)dp = [float('inf')] * (len(s) + 1)dp[0] = 0for i in range(1, len(s)+1):for j in range(i):if Palin[j][i-1]:dp[i] = min(dp[j] + 1, dp[i])return dp[len(s)] - 1def isPalindrom(self, s):n = len(s)dp = [[False] * n for _ in range(n)]for mid in range(n):i = j = midwhile i >= 0 and j <= n-1 and s[i] == s[j]:dp[i][j] = Truei -= 1j += 1i = midj = mid + 1while i >= 0 and j <= n-1 and s[i] == s[j]:dp[i][j] = Truei -= 1j += 1return dp