【LeetCode最详尽解答】125-验证回文串 Valid-Palindrome

本文主要是介绍【LeetCode最详尽解答】125-验证回文串 Valid-Palindrome，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接:

125-验证回文串

直觉

这个问题需要使用一些内置函数，比如 s[l].isalnum() 和 s[l].lower()。基本要求简单明了。

例子:

输入: s = "A man, a plan, a canal: Panama"

输出: true

解释: "amanaplanacanalpanama" 是一个回文。

我们可以设置两个指针：一个在输入的开始位置，另一个在末尾位置。左指针始终应小于右指针，因为如果它们在同一位置，我们不需要比较它们。如果左指针大于右指针，这没有意义，并且会生成重复的比较。

我们应该跳过非字母数字字符。如果最初左指针指向一个非字母数字字符，我们应该将其右移，直到遇到第一个字母数字字符。然而，我们不应该继续右移；我们应确保左指针始终小于右指针并且不越界。右指针同样适用。当它们到达正确的位置时，我们将字符转换为小写值并进行比较。如果它们不相同，我们直接返回 False。如果它们相同，我们调整左指针和右指针到新的位置并继续循环。如果我们遍历所有的值，我们只需返回 True。

方法

设置两个指针，left 和 right。
初始化它们分别为 0 和 len(s) - 1。
确保左指针小于右指针，以避免越界。
比较左指针和右指针处字符的值。
如果左指针不是字母数字字符，将其右移；右指针同理。
比较字符的小写值。如果它们不相同，返回 False。
如果它们相同，移动左指针和右指针并继续循环。

复杂度

时间复杂度:
$O (n)$
- 该算法最多遍历字符串中的每个字符一次，时间复杂度为线性。
空间复杂度:
$O (1)$
- 该算法使用的额外空间是常数，无论输入大小如何。

代码

class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""l = 0r = len(s) - 1while l < r:while l < r and not s[l].isalnum():l+=1while l < r and not s[r].isalnum():r-=1if s[l].lower() != s[r].lower():return Falsel+=1r-=1return True