leetcode [132] 分割回文串 II

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

class Solution:
    def minCut(self, s: str) -> int:
        if len(s) == 0:
            return 0
        dp = [i for i in range(len(s) + 1)]
        dp[0] = -1
        for i in range(1, len(dp)):
            # dp[i] = min(dp[i], dp[i - 1] + 1)
            # odd
            left, right = i - 1, i - 1
            while left >= 0 and right < len(s) and s[left] == s[right]:
                dp[right + 1] = min(dp[right + 1], dp[left] + 1)
                left -= 1
                right += 1
            
            # even
            left, right = i - 1, i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                dp[right + 1] = min(dp[right + 1], dp[left] + 1)
                left -= 1
                right += 1

        return dp[-1]