[LeetCode]132 分割回文段II

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。

示例

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

思路

  • 动态规划
  • 『难以言表』看代码吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == s[::-1]:
            return 0
        s_len = len(s)
        for i in range(1, s_len+1):
            if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                return 1
            
        mem = [i for i in range(-1, s_len)]
        for i in range(1, s_len+1):
            # 尝试从j处分割
            for j in range(i):
                if s[j:i] == s[j:i][::-1]:
                    mem[i] = min(mem[i], mem[j] + 1) 
        return mem[-1]