125. 验证回文串 Easy

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

解题思路

输入：一个字符列表 s

输出：验证是否是回文字符串

本题是典型的 相向双指针 问题。

我们可以定义两个指针：left = 0，right = len(s) - 1，分别指向字符串的开头和结尾。

然后进行如下操作：

• 当 left < right 时，过滤掉非字母和数字的字符
• 当发现 s[left].lower() == s[right].lower() 继续向中间靠拢
• 否则直接返回 False
• 当循环结束都没有返回则说明是回文串

代码实现

python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1  # 定义左右指针

        while left < right:
            # 左指针跳过非字母数字字符
            while left < right and not s[left].isalnum():
                left += 1
            
            # 右指针跳过非字母数字字符
            while left < right and not s[right].isalnum():
                right -= 1

            # 比较当前字符（统一转小写）是否相等
            if s[left].lower() != s[right].lower():
                return False  # 有不同则不是回文串

            # 移动左右指针继续比较
            left += 1
            right -= 1

        return True  # 所有字符匹配，返回 True

javascript

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        while (!/[a-z|A-Z|0-9]/.test(s[left]) && left < right) {
            left++;
        }

        while (!/[a-z|A-Z|0-9]/.test(s[right]) && left < right) {
            right--;
        }

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false
        }

        left++;
        right--;
    }

    return true;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

125 国际版

125 中文版