LeetCode 680验证回文串 II一、题目给定一个字符串s最多可以删除一个字符判断删除后能否成为回文串。例如s aba → True s abca → True s abc → False二、核心概念什么是回文串回文串Palindrome正着读和反着读完全一样的字符串。例如aba abba racecar都是回文串。判断回文最常用的方法L → ← R a b c d c b a ↑ ↑使用两个指针L从左往右R从右往左比较s[L]s[R]如果相同就继续向中间移动。三、这道题和普通回文题有什么区别普通的回文判断只要发现s[L] ! s[R]直接False。但是本题允许最多删除一个字符。所以当s[L]!s[R]时不能直接返回False。因为我们还可以删除一个字符。此时只有两种可能① 删除左边字符isPalindrome(s,L1,R)② 删除右边字符isPalindrome(s,L,R-1)只要其中一个成立即可AorB四、为什么只需要删除 L 或 R这是本题最重要的思维。假设a b c a ↑ ↑ L R发现b ! c如果最终能够变成回文那么b和c不可能同时保留。因为它们现在处于应该互相对应的位置但b ! c所以必须删除其中一个。因此只需要尝试删除 s[L]或者删除 s[R]不需要尝试其他位置。五、整体算法使用双指针 回文判断。第一步设置L0Rlen(s)-1从字符串两端开始。第二步如果s[L]s[R]说明当前两个字符没问题L1R-1继续向中间走。第三步如果s[L]!s[R]说明出现了第一个冲突。尝试删除 L或者删除 R只要一个成功就返回True。第四步如果一直没有冲突returnTrue说明原字符串本身就是回文串不需要删除任何字符。六、代码classSolution:defisPalindrome(self,s,left,right):whileleftright:ifs[left]!s[right]:returnFalseleft1right-1returnTruedefvalidPalindrome(self,s:str)-bool:left0rightlen(s)-1whileleftright:ifs[left]s[right]:left1right-1else:return(self.isPalindrome(s,left1,right)orself.isPalindrome(s,left,right-1))returnTrue七、代码逐部分理解1.isPalindrome()defisPalindrome(self,s,left,right):作用判断s[left]到s[right]这一部分是不是回文。例如isPalindrome(s,2,6)就是检查s[2] ~ s[6]这一段。2. 判断回文whileleftright:两个指针不断向中间移动。如果s[left]!s[right]直接returnFalse如果一直没有发现不一样returnTrue八、最关键的代码return(self.isPalindrome(s,left1,right)orself.isPalindrome(s,left,right-1))可以翻译成如果删除左边的字符后是回文或者删除右边的字符后是回文那么答案就是True。其中left1表示跳过s[left]相当于删除左边字符。而right-1表示跳过s[right]相当于删除右边字符。九、例子abca字符串下标 0 1 2 3 字符 a b c a ↑ ↑ L R第一轮a a所以L1R-1变成a b c a ↑ ↑ L R发现b ! c此时有两个选择。方案一删除 ba c a是回文。所以True方案二删除 ca b a也是回文。最终abca → True十、为什么使用or因为题目是最多删除一个字符。不是要求两种删除方式都必须成功。只需要一种方式成功即可。所以AorB而不是AandB例如删除左边 → True 删除右边 → False那么True or False True所以答案仍然是True。十一、我这次遇到的问题self我原来的代码classSolution:defisPalindrome(s,left,right):...这里少了self正确defisPalindrome(self,s,left,right):十二、为什么需要self因为isPalindrome()写在classSolution:里面它是Solution的实例方法。当我们这样调用self.isPalindrome(s,l1,r)Python 会自动把当前对象self传进去。实际上相当于Solution.isPalindrome(self,s,l1,r)所以函数定义必须能够接收self s left right一共 4 个参数。十三、我的错误在哪里错误写法defisPalindrome(s,left,right):只有s left right3 个参数。但调用self.isPalindrome(s,l1,r)时Python 实际传入self s l 1 r4 个参数。因此会出现参数数量不匹配的问题。十四、记住 Python 的这个规律在classSolution:里面定义普通实例方法时def函数名(self,参数1,参数2,...):例如classSolution:defadd(self,a,b):returnab调用self.add(1,2)这里self不需要我们手动传。十五、while left right有没有问题你原来写whileleftright:实际上可以运行逻辑也没问题。但是更推荐whileleftright:原因是当left right说明两个指针已经来到同一个字符。例如a b c b a ↑ L/R中间的字符不需要和自己比较。所以whileleftright:更加自然。十六、这道题的知识点总结算法双指针Two Pointers辅助思想递归/函数复用式地检查剩余区间是否为回文严格来说你这里并没有真正进行递归因为isPalindrome()本身没有调用自己。核心操作left1right-1第一次遇到不同字符s[left]!s[right]尝试isPalindrome(s,left1,right)或者isPalindrome(s,left,right-1)最终判断AorB十七、时间复杂度外层双指针最多走一遍O(n)遇到冲突后最多额外检查两次剩余字符串。所以整体仍然是时间复杂度O(n)空间复杂度O(1)因为只使用了几个指针没有创建新的字符串。十八、这道题最应该记住的模板以后遇到最多删除一个字符 判断回文直接想到left0rightlen(s)-1whileleftright:ifs[left]s[right]:left1right-1else:# 第一次出现冲突# 删除左边 OR 删除右边return(isPalindrome(left1,right)orisPalindrome(left,right-1))returnTrue最核心的就是这一句话左右相同就继续向中间走左右不同就尝试跳过左边或右边只要一种情况能形成回文即可。十九、你的本次学习重点你这次其实已经自己写出了正确的算法框架主要问题不是算法而是 Python 语法算法 双指针 → 正确 发现冲突 → 左右各尝试一次 → 正确 使用 or → 正确 回文判断函数 → 正确 Python 实例方法缺少 self → 需要注意所以这道题你应该重点掌握两个东西算法层面双指针 遇到冲突时尝试删除左/右Python 层面class 里的实例方法 def xxx(self, ...):而不是def xxx(...):这两个知识点掌握了这道题就真正学会了。你后面刷题时可以把**“遇到冲突 → 跳过左边 / 跳过右边”**当成这道题的核心记忆点而不是死记整段代码。