难度: Hard
Submission
运行时间: 116 ms
内存: 17.9 MB
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
# 时间复杂度：O(n^2) 空间复杂度：O(n^2)
# 获取字符串的长度
n = len(s)
# 如果允许删除的字符数加1大于等于字符串的长度，直接返回True
if 1 + k >= n: return True
# 初始化动态规划数组，dp[i][j]表示s[i:j+1]子串成为回文串需要删除的最小字符数
dp = [[0] * n for _ in range(n)]
# 从字符串的倒数第二个字符开始遍历到第一个字符
for left in range(n - 2, -1, -1):
# 初始化dp[left][left] = 1，单个字符是回文串
dp[left][left] = 1
# 对于left位置的每个右边界right进行遍历
for right in range(left + 1, n):
# 如果当前的字符相同，则dp[left][right]等于它们中间部分的dp值加2
if s[left] == s[right]:
dp[left][right] = dp[left + 1][right - 1] + 2
# 如果不同，则dp[left][right]取左边或右边去掉一个字符后的最大值
else:
dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
# 如果当前dp值大于等于n-k，意味着可以通过删除不超过k个字符使得s成为回文串，返回True
if dp[left][right] >= n - k:
return True
# 遍历结束后，如果没有找到符合条件的情况，返回False
return False
Explain
这道题目的解法使用了动态规划的思路来处理问题。首先定义了一个二维数组dp，其中dp[i][j]表示为了使子字符串s[i:j+1]成为回文串需要删除的最小字符数。算法从字符串的后端开始遍历，通过比较字符是否相同来递推填充dp数组。如果字符相同，dp[i][j]则由dp[i+1][j-1]决定，并增加2表示两端字符相同。如果字符不同，则考虑删除左端或右端字符的情况，取两者中较大的值。过程中，如果任何dp[i][j]的值大于等于n-k（k为允许删除的最大字符数），则返回True，表示可以通过删除不超过k个字符使得s成为回文串。如果遍历完所有字符对都没有返回True，则最后返回False。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
# 获取字符串的长度
n = len(s)
# 如果允许删除的字符数加1大于等于字符串的长度，直接返回True
if 1 + k >= n: return True
# 初始化动态规划数组，dp[i][j]表示s[i:j+1]子串成为回文串需要删除的最小字符数
dp = [[0] * n for _ in range(n)]
# 从字符串的倒数第二个字符开始遍历到第一个字符
for left in range(n - 2, -1, -1):
# 初始化dp[left][left] = 1，单个字符是回文串
dp[left][left] = 1
# 对于left位置的每个右边界right进行遍历
for right in range(left + 1, n):
# 如果当前的字符相同，则dp[left][right]等于它们中间部分的dp值加2
if s[left] == s[right]:
dp[left][right] = dp[left + 1][right - 1] + 2
# 如果不同，则dp[left][right]取左边或右边去掉一个字符后的最大值
else:
dp[left][right] = max(dp[left + 1][right], dp[left][right - 1])
# 如果当前dp值大于等于n-k，意味着可以通过删除不超过k个字符使得s成为回文串，返回True
if dp[left][right] >= n - k:
return True
# 遍历结束后，如果没有找到符合条件的情况，返回False
return False
Explore
在动态规划数组`dp`中，`dp[i][i]`代表的是子字符串s[i:i+1]，即只包含单个字符的字符串。单个字符的字符串本身就是一个回文串，其不需要删除任何字符就已经是回文。因此，`dp[i][i]`的值应该设定为0，代表不需要删除任何字符。如果题解中设定为1，这可能是一个错误或者误解。正确的初始化应该是`dp[i][i] = 0`。
在题解中，当`s[left]`不等于`s[right]`时，选择取`dp[left + 1][right]`和`dp[left][right - 1]`中的最大值是一个错误。实际上，应该选取这两者中的最小值。原因是我们希望找到使子字符串成为回文串所需的最少删除字符数。`dp[left + 1][right]`代表删除左侧字符后的最小删除数，而`dp[left][right - 1]`代表删除右侧字符后的最小删除数。取这两者的最小值能确保我们以最少的删除次数达成目标。
题解中的这部分逻辑是正确的。在这个算法中，`dp[left][right]`表示的是为使子字符串`s[left:right+1]`成为回文串而需要的最少字符删除数。如果`dp[left][right]`的值大于等于`n-k`，这意味着剩余的字符数（即`n - dp[left][right]`）是大于等于`k`的。因此，我们可以确保在删除至多`k`个字符的情况下，字符串`s`可以被转换为一个回文串。
题解中并没有特别提到对特殊字符或空字符串的特别处理。然而，动态规划算法本身是泛化的，能够处理任何类型的字符，包括特殊字符。对于空字符串，由于其已经是回文且不需要任何删除，算法应当直接返回True。这是因为空字符串不需要任何操作即是回文，且k的值在此情况下不影响结果。