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 是一个空字符串 ""。
由于空字符串正着读和反着读都一样，所以是回文串。

提示：

  • 1 <= s.length <= 2 * 10^5
  • s 仅由可打印的 ASCII 字符组成

解题思路

这道题有两种主要思路：

方法一：预处理 + 双指针（推荐） 使用双指针从字符串两端向中间遍历，在遍历过程中动态跳过非字母数字字符。遇到字母时转换为小写进行比较。这种方法空间复杂度更优，因为不需要额外存储处理后的字符串。

具体步骤：

  1. 初始化左右两个指针，分别指向字符串的开头和结尾
  2. 移动左指针直到遇到字母数字字符，同样移动右指针
  3. 将两个字符转换为小写后比较，如果不相等则返回false
  4. 继续移动指针直到它们相遇

方法二：先处理后比较 先遍历整个字符串，提取所有字母数字字符并转换为小写，然后使用双指针判断处理后的字符串是否为回文。这种方法思路更直观，但需要额外的空间存储处理后的字符串。

两种方法的时间复杂度都是O(n)，但方法一的空间复杂度更优，因此推荐使用方法一。

代码实现

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            // 跳过非字母数字字符
            while (left < right && !isalnum(s[left])) {
                left++;
            }
            while (left < right && !isalnum(s[right])) {
                right--;
            }
            
            // 转换为小写后比较
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
};

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

public class Solution {
    public bool IsPalindrome(string s) {
        int left = 0, right = s.Length - 1;
        
        while (left < right) {
            // 跳过非字母数字字符
            while (left < right && !char.IsLetterOrDigit(s[left])) {
                left++;
            }
            while (left < right && !char.IsLetterOrDigit(s[right])) {
                right--;
            }
            
            // 转换为小写后比较
            if (char.ToLower(s[left]) != char.ToLower(s[right])) {
                return false;
            }
            
            left++;
            right--;
        }
        
        return true;
    }
}

var isPalindrome = function(s) {
    let left = 0, right = s.length - 1;
    
    while (left < right) {
        // 跳过非字母数字字符
        while (left < right && !/[a-zA-Z0-9]/.test(s[left])) {
            left++;
        }
        while (left < right && !/[a-zA-Z0-9]/.test(s[right])) {
            right--;
        }
        
        // 转换为小写后比较
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每个字符最多被访问一次
空间复杂度O(1)只使用了常数级别的额外空间存储指针变量

相关题目