223 - 132 分割回文串
题目
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab" 输出: 1 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
解答
最坏情况,按照每个字母分割
class Solution:
def minCut(self, s: str) -> int:
min_s = list(range(len(s)))
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
for j in range(i+1):
if s[i] == s[j] and (i-j < 2 or dp[j+1][i-1]):
dp[j][i] = True
if j == 0:
min_s[i] = 0
else:
min_s[i] = min(min_s[i], min_s[j-1]+1)
return min_s[-1]
Runtime: 408 ms, faster than 66.52% of Python3 online submissions for Palindrome Partitioning II.
Memory Usage: 29.5 MB, less than 90.00% of Python3 online submissions for Palindrome Partitioning II.
李威威大佬的题解
dp表示最小分割次数
状态转移:
遍历j到i,如果s[j+1: i]是回文,那么就在dp[j]的基础上多分割一次即可
class Solution:
def minCut(self, s: str) -> int:
size = len(s)
if size < 2:
return 0
dp = [i for i in range(size)]
checked = [[False for _ in range(size)] for _ in range(size)]
for right in range(size):
for left in range(right+1):
if s[left] == s[right] and (right-left <= 2 or
checked[left+1][right-1]):
checked[left][right] = True
for i in range(1, size):
if checked[0][i]:
dp[i] = 0
continue
dp[i] = min([dp[j]+1 for j in range(i) if checked[j+1][i]])
return dp[size-1]
Runtime: 468 ms, faster than 59.74% of Python3 online submissions for Palindrome Partitioning II.
Memory Usage: 31.2 MB, less than 80.00% of Python3 online submissions for Palindrome Partitioning II.
Last updated
Was this helpful?