题目内容

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

说明：本题中，我们将空字符串定义为有效的回文串。

示例

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true
解释：”amanaplanacanalpanama” 是回文串
示例 2:

输入: “race a car”
输出: false
解释：”raceacar” 不是回文串

提示

1、1 <= s.length <= 2 * 10^5
2、字符串 s 由 ASCII 字符组成

题解

本题可以用双指针算法来求解。具体，定义两个指针i和j，然后i从0开始，j从s.size()-1开始，i往右，j往左，每次比较指针指向的字符是否相等。如果一旦不等，直接返回false，否则一直匹配下去，直到两个指针相遇或到中间的地方算法停止。

代码

class Solution {
public:
    bool isPalindrome(string s) {
        for(int i = 0,j = s.size()-1;i<j;i++,j--){
            while(i<j && !check(s[i])) i++;//判断字符是否合规，将类似:,等标点以及其他字符略过
            while(i<j && !check(s[j])) j--;//判断字符是否合规，将类似:,等标点以及其他字符略过
            if(i < j && tolower(s[i]) != tolower(s[j])) return false;//每次比较字符是否一致
        }
        return true;
    }   
    
    bool check(char c){
        return c >= 'a' && c <='z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9';
    }
};