125. 验证回文串

难度：简单

题目

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

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

示例 1：

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2：

输入: "race a car"
输出: false

Reference

题解

基本思路： 使用双指针法进行处理，需要注意如下特殊情况

1. 需要忽略字符串中的符号而只考虑字母和数字
2. 大小写的ASCII数值相差32，但ASCII数值相差32的两个字符不一定是大小写关系，如'0'(48)与'P'(80)

代码如下：

bool isText(char s)
{
    return (s >= 'A' && s <= 'Z') || (s >= 'a' && s <= 'z') || (s >= '0' && s <= '9');
}
bool isSame(char s1, char s2)
{
    return (s1 == s2) || (s2 >= 'A' && s1 - s2 == 32) || (s1 >= 'A' && s2 - s1 == 32);
}
bool isPalindrome(char * s){
    int len = strlen(s), head = 0, tail = len - 1;
    while (head < len && !isText(s[head]))
        head++;
    while (tail >= 0 && !isText(s[tail]))
        tail--;
    while(tail > head && head < len && tail >= 0)
    {
        if (!isSame(s[head], s[tail]))
            return false;
        head++;
        tail--;
        while (!isText(s[head]))
            head++;
        while (!isText(s[tail]))
            tail--;
    }
    return true;
}

评论