目录

LeetCode 132 Palindrome Partitioning ||分析Code欢迎一起来参与leetcode刷题项目

LeetCode 132 Palindrome Partitioning ||

分析

这是一道动态规划题，基本上需要考虑一个字符串的子字符串的题目，都能往动归上考虑（子问题）。 举例子： 现在假设我们有一个字符串

# 长度为8 abcdaaaa # 它有如下几种分法 abcd aaaa j i abcda aaa j i abcdaa aa j i abcdaaa a j i abcdaaaa # 最后一行，j i 重合了

我们把它看作左半部分和右半部分，现在，问题的答案就变成了把左半部分分解所需的步数再加1 用**f[i]**表示把长度为i的字符串分解所需的最小步数

if s[i, j+1]是一个回文子串： f[i] = min(f[i], f[j]+1)

现在问题就变成了如何判断一个子串是不是回文的？？？ 在python里，这个有小技巧的

s[i:j+1] == s[i:j+1][::-1]

不过这种小技巧会复制子串。 此处写一个动归算法来判断子串是否回文

# left, right # c[l][r]表示，l,r这个区间里的子串是否回文 c[l][r] = s[l] == s[r] and l+1 > r-1 or c[l+1][r-1] # c[l+1][r-1]就是已经解决的子问题

Code

class Solution: def minCut(self, s: str) -> int: n = len(s) c = [[False] * n for _ in range(n)] # 为了判断回文子串 for i in range(1, n+1): for j in range(n+1-i): l, r = j, j+i-1 tag = l+1 > r-1 or c[l+1][r-1] c[l][r] = s[l] == s[r] and tag f = [2**31] * (n+1) f[0] = 0 # 保证从f[0]转移 for i in range(1, n+1): for j in range(1, i+1): if c[j-1][i-1]: f[i] = min(f[i], f[j-1]+1) # print(c) return f[n]-1 # 减一是因为，我这里定义最少能分割成多少个子串 # 答案是要求出剪几刀

欢迎一起来参与leetcode刷题项目

刷题的GitHub: github链接.