image.png
0. 链接
1. 题目
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Example:
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
2. 思路1: 动态规划
- 基本思路是:
- 先初始化最差情形，即dp[i] = i(i = 0~size-1), 即每个字母都自成一个回文, dp[i]表示从0到i构成的字符串划分为回文最少需要切几刀
- 再自
i=1开始从左到右依次尝试以每个字母作为回文的中心点, 对于每个中心点mid, 向左向右尽量扩展到start,end, 每左右各扩展一格, 则更新dp[end] = min(dp[end], 1 + dp[start - 1] if start > 0 else 0), 表示截止到end所需切的最少刀数, 取决于当前是否选择切这一刀，选择的依据，就是能否使得dp[end]变小，这是典型的动态规范思路，即选择，并评价选择的结果优劣。 - 需要注意的是，对于中心点的选择，有可能是一个，也有可能是2个，比如
abba回文就需要拿中间的bb作为中心点,往左往右可扩展方可, 处理方式即start, end = mid - 1, mid, 它担负的任务与上一步中一样，也是要尽量扩展回文长度, 然后尽量缩小dp[end]的值 - 最终只需要返回
dp[size-1]即可
- 分析:
- 过程中需要尝试以每个字母作为中心点的情形, 所以有一个n次循环, 对于每个中心点, 又要有左右扩展的尝试, 极端情况下，比如
aaaaaa的情形，每次左右扩展, 都可能到边界, 因此也是一个n次循环, 最终时间复杂度是O(n^2), 空间复杂度是O(n)
- 复杂度
- 时间复杂度
O(n^2) - 空间复杂度
O(n)
3. 代码
# coding:utf8
class Solution:
def minCut(self, s: str) -> int:
size = len(s)
dp = [[False] * size for _ in range(size)]
min_cut_times = None
def dfs(s, start, size, dp, cut_times):
nonlocal min_cut_times
if start == size:
if min_cut_times is None or min_cut_times > cut_times - 1:
min_cut_times = cut_times - 1
else:
for i in range(start, size):
if s[i] != s[start]:
continue
if i - 1 > start + 1 and not dp[i - 1][start + 1]:
continue
dp[i][start] = True
dfs(s, i + 1, size, dp, cut_times + 1)
dfs(s, 0, size, dp, 0)
return min_cut_times
def my_test(solution, s):
print('input: s={}; output: {}'.format(s, solution.minCut(s)))
solution = Solution()
my_test(solution, 'aab')
my_test(solution, 'bb')
输出结果
input: s=aab; output: 1
input: s=bb; output: 0
4. 结果
image.png
