给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 2 * 105

  • 字符串 s 由 ASCII 字符组成

思路

  • 双指针直接判断

  • 静态boolean数组标识

代码

  • 双指针直接判断

class Solution {
    public boolean isPalindrome(String str) {
        if (str == null) {
            return true;
        }

        int head = 0, tail = str.length() - 1;
        while (head < tail) {
            char c1 = str.charAt(head);
            char c2 = str.charAt(tail);

            if (!((c1 >= 48 && c1 <= 57) || (c1 >= 'a' && c1 <= 'z') || (c1 >= 'A' && c1 <= 'Z'))) {
                head++;
                continue;
            }

            if (!((c2 >= 48 && c2 <= 57) || (c2 >= 'a' && c2 <= 'z') || (c2 >= 'A' && c2 <= 'Z'))) {
                tail--;
                continue;
            }
            
            if (c1 >= 'a') {
                c1 -= 32;
            }
            if (c2 >= 'a') {
                c2 -= 32;
            }

            if (c1 != c2) {
                return false;
            }

            head++;
            tail--;
        }
        return true;
    }
}

  • 静态boolean数组标识

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left <= right) {
            int leftNum = s.charAt(left);
            int rightNum = s.charAt(right);
            if (!IS_PALINDROME_FLAGS[leftNum]) {
                left++;
                continue;
            }
            if (!IS_PALINDROME_FLAGS[rightNum]) {
                right--;
                continue;
            }
            if (leftNum > 96) {
                leftNum -= 32;
            }
            if (rightNum > 96) {
                rightNum -= 32;
            }
            if (leftNum != rightNum) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    private static final boolean[] IS_PALINDROME_FLAGS = new boolean[128];

    static {
        for (int i = 48; i <= 57; i++) {
            IS_PALINDROME_FLAGS[i] = true;
        }
        for (int i = 65; i <= 90; i++) {
            IS_PALINDROME_FLAGS[i] = true;
        }
        for (int i = 97; i <= 122; i++) {
            IS_PALINDROME_FLAGS[i] = true;
        }
    }
}