难度: Easy
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1:
输入: s = "aba" 输出: true
示例 2:
输入: s = "abca" 输出: true 解释: 可以删除 "c" 字符 或者 "b" 字符
示例 3:
输入: s = "abc" 输出: false
提示:
1 <= s.length <= 105s 由小写英文字母组成注意：本题与主站 680 题相同： https://leetcode-cn.com/problems/valid-palindrome-ii/
运行时间: 40 ms
内存: 16.1 MB
class Solution:
def validPalindrome(self, s: str) -> bool:
if s==s[::-1]:
return True
left=0
right=len(s)-1
while left<right:
if s[left]==s[right]:
left+=1
right-=1
else:
s_left=s[left:right]
s_right=s[left+1:right+1]
return s_left==s_left[::-1] or s_right==s_right[::-1]
此题解首先检查字符串是否已经是回文；如果是，则直接返回true。如果不是回文，使用双指针技术从字符串的两端开始向中间检查。当遇到不匹配的字符时，考虑两种情况：一是删除左侧字符，二是删除右侧字符。对于每种情况，生成新的子字符串并检查是否为回文。如果其中一种情况导致子字符串成为回文，则原字符串可以通过删除一个字符成为回文。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def validPalindrome(self, s: str) -> bool:
# 检查s是否为回文
if s == s[::-1]:
return True
left = 0
right = len(s) - 1
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
else:
# 尝试删除左侧或右侧字符
s_left = s[left:right]
s_right = s[left+1:right+1]
# 检查是否任一情况下的子字符串是回文
return s_left == s_left[::-1] or s_right == s_right[::-1]
在Python中，字符串的反转和比较操作非常高效，因为这些操作都是在底层进行优化的。使用s == s[::-1]这种方式可以直接利用Python的内置功能，代码简洁且易于理解。虽然双指针方法在理论上能够提供相同的效率（O(n)时间复杂度），但在实际编码中，使用内置的字符串操作可以减少代码复杂度和出错的可能性。
生成两个子字符串进行再次回文验证是一种直接且有效的方法，它避免了递归带来的额外复杂性和可能的性能问题。递归方法通常需要更多的内存（栈空间）并且可能导致更深的调用栈，特别是在字符串较长时。通过创建两个子字符串，我们可以立即检查每个字符串是否为回文，这种方法简单且在时间复杂度上通常是可以接受的。此外，这种方法使得代码的逻辑更为清晰和直接。
在遇到不匹配的字符时，我们需要考虑通过删除一个字符来尝试形成回文。s_left = s[left:right]表示删除右侧不匹配的字符，因为right索引是不包括在内的。而s_right = s[left+1:right+1]表示删除左侧不匹配的字符，通过将left索引向右移动一位来实现。这两种取值范围确保我们可以通过删除任一边的一个字符来检查剩余部分是否为回文。