难度: Easy
给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
示例 1：
输入：s = "aba" 输出：true
示例 2：
输入：s = "abca" 输出：true 解释：你可以删除字符 'c' 。
示例 3：
输入：s = "abc" 输出：false
提示：
1 <= s.length <= 105s由小写英文字母组成
Submission
运行时间: 42 ms
内存: 16.2 MB
class Solution:
def validPalindrome(self, s: str) -> bool:
if s == s[::-1]:
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
else:
lefts = s[:left] + s[left+1:]
rights = s[:right] + s[right+1:]
return lefts == lefts[::-1] or rights == rights[::-1]
return True
Explain
这个题解采用了双指针的思路。首先判断原字符串是否是回文串，如果是，直接返回 True。如果不是，则使用两个指针 left 和 right 分别指向字符串的首尾。当左右指针指向的字符相等时，同时向中间移动；当遇到不相等的字符时，尝试删除左指针或右指针指向的字符，判断删除后的子串是否是回文串。如果删除任意一个字符后可以形成回文串，则返回 True，否则返回 False。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def validPalindrome(self, s: str) -> bool:
# 如果原字符串是回文串，直接返回 True
if s == s[::-1]:
return True
left, right = 0, len(s) - 1
while left < right:
# 左右指针指向的字符相等，继续向中间移动
if s[left] == s[right]:
left += 1
right -= 1
else:
# 尝试删除左指针或右指针指向的字符，判断删除后的子串是否为回文串
lefts = s[:left] + s[left+1:]
rights = s[:right] + s[right+1:]
return lefts == lefts[::-1] or rights == rights[::-1]
return True
Explore
在本题解中，一旦遇到不匹配的字符，尝试通过删除左指针或右指针指向的字符来解决问题。这里使用了字符串切片来生成新的子串，并直接检查新子串是否为回文串。实际上，可以继续使用双指针策略来检查切片后的子串是否为回文，这样可以避免生成新的字符串，从而优化内存使用和可能的性能损失。不过，为了简化代码和直观展示思路，题解选择了直接使用字符串反转的方法来判断回文。
在Python中，字符串切片操作虽然方便，但在处理非常大的字符串时可能会导致显著的内存使用和性能损耗，因为它会创建原字符串的一个新副本。一种更高效的方法是继续使用双指针技术：在确定要删除一个字符后，根据删除点将双指针向内移动，然后继续检查剩余部分是否为回文。这样可以避免创建额外的字符串副本，只需在原字符串上操作，大幅减少内存和时间消耗。
在验证可能的回文串时，单纯删除左指针或右指针指向的字符可能不足以确保找到正确的解决方案。例如，在字符串 'abca' 中，如果只选择删除 'b'（左指针指向的字符），则剩余 'aca' 仍然是回文；但如果只选择删除 'c'（右指针指向的字符），剩余 'aba' 也是回文。因此，为了全面验证，需要检查两种可能性。这确保了在面对不同情况时，能够找到所有可能的回文结构。
题目允许删除一个字符来尝试形成回文串，这意味着即便中间部分验证为非回文，仍有可能通过删除一个恰当的字符使得整个字符串成为回文。这是题目的特殊要求之一，即允许一次删除操作来达成回文的条件。因此，即使遇到非回文的中间部分，我们也需要继续探索删除一个字符的可能性，来找到可能的回文解决方案。