描述

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。

示例

示例 1:

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

示例 2:

输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串

提示

  • 1 <= s.length <= 2 * 105
  • 字符串 s 由 ASCII 字符组成

解题思路

  • 判断回文的思路很简单，直接用双指针，遍历一遍字符串。模板是：

    int left = 0, right = n - 1; //左指针从字符串第一个字符开始，右指针从字符串最后一个字符开始；
while (left < right) { //当 left < right 时，遍历字符串
  if (s.charAt(left) != s.charAt(right)) {
      return false; //如果不满足对应位置字符相等，直接返回 fasle;
  }
  left++;
  right--;
}
return true;

  • 题目要求只考虑字母和数字字符，可以忽略字母的大小写。所以我们需要一些特殊的处理。

    • 对于不是字母或数字的字符，直接跳过

      if (!Character.isLetterOrDigit(s.charAt(left))) {
   left++;
   continue;
}

    • 比较字符时，忽略大小写的方法：

      String.valueOf(s.charAt(left)).equalsIgnoreCase(String.valueOf(s.charAt(right)))

      代码

      class Solution {
public boolean isPalindrome(String s) {
   int n = s.length();
   if (n == 0) return true;
   int left = 0, right = n - 1;
   while (left < right) {
       if (!Character.isLetterOrDigit(s.charAt(left))) {
           left++;
           continue;
       } else if (!Character.isLetterOrDigit(s.charAt(right))) {
           right--;
           continue;
       }
       if (!String.valueOf(s.charAt(left)).equalsIgnoreCase(String.valueOf(s.charAt(right)))) {
           return false;
       }
       left++;
       right--;
   }
   return true;
}
}