Description
Given a string s and an integer k, return true if s is a k-palindrome.
A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.
Example 1:
Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.
Example 2:
Input: s = "abbababa", k = 1
Output: true
Constraints:
1 <= s.length <= 1000
s consists of only lowercase English letters.
1 <= k <= s.length
Solution
Recursive
Similar to 680. 验证回文字符串 Ⅱ, this time we could delete k characters.
Similarly, use recursive + memo.
Time complexity:
o
(
n
k
)
o(nk)
o(nk)
Space complexity:
o
(
n
k
)
o(nk)
o(nk)
Longest Palindromic Sequence
We can find the longest palindromic sequence in s, and if len(longest_palindromic_sequence) + k > len(s), that means even after deleting k characters, the string is still not palindromic.文章来源：https://www.toymoban.com/news/detail-834632.html
Time complexity:
o
(
n
2
)
o(n^2)
o(n2)
Space complexity:
o
(
n
2
)
o(n^2)
o(n2)文章来源地址https://www.toymoban.com/news/detail-834632.html
Code
Recursive
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
memo = {}
def helper(left: int, right: int, k: int) -> bool:
if (left, right, k) in memo:
return memo[(left, right, k)]
while left <= right:
if s[left] == s[right]:
left += 1
right -= 1
elif k > 0:
res = helper(left + 1, right, k - 1) or helper(left, right - 1, k - 1)
break
else:
res = False
break
memo[(left, right, k)] = res if left <= right else True
return memo[(left, right, k)]
return helper(0, len(s) - 1, k)
Longest Palindromic Sequence
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
def longest_palindromic_sequence(s: str) -> int:
dp = [[0] * len(s) for _ in range(len(s))]
# init
for i in range(len(s)):
dp[i][i] = 1
# dp
for i in range(len(s) - 2, -1, -1):
for j in range(i + 1, len(s)):
if s[i] == s[j]:
dp[i][j] = 2 + dp[i + 1][j - 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][len(s) - 1]
lps = longest_palindromic_sequence(s)
return len(s) - lps <= k
到了这里，关于leetcode - 1216. Valid Palindrome III的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
