📃 题目描述

题目链接：

• 剑指 Offer II 018. 有效的回文 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 125. 验证回文串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

示例 1:

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

🔔 解题思路

比较简单，判断一个字符串是不是回文，常用的方法就是使用双指针。可以定义两个指针，一个指针从第 1 个字符开始从前向后移动，另一个指针从最后一个字符开始从后向前移动。如果两个指针指向的字符相同，则同时移动这两个指针以判断它们指向的下一个字符是否相同。这样一直移动下去，直到两个指针相遇。

由于两个指针移动的总次数最多等于字符串的长度，因此该解法的时间复杂度是 O(N)

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return true;
        }

        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            char ch1 = s.charAt(left);
            char ch2 = s.charAt(right);
            if (!Character.isLetterOrDigit(ch1)) {
                left ++;
                continue;
            }
            if (!Character.isLetterOrDigit(ch2)) {
                right --;
                continue;
            }

            ch1 = Character.toLowerCase(ch1);
            ch2 = Character.toLowerCase(ch2);
            if (ch1 != ch2) {
                return false;
            }
            else {
                left ++;
                right --;
            }
        }

        return true;
    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(N)