欢迎访问LeetCode题解合集

题目描述

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

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

示例 1:

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

示例 2:

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

题解：

双指针判断回文串。

法一：

将 s 中的数字和字母保存为 t ，然后判断 t 是否是回文串。

时间复杂度：$O(n)$

额外空间复杂度：$O(n)$

class Solution {
public:
    bool isPalindrome(string s) {
        string t = "";
        for ( auto& it : s ) {
            if ( isdigit(it) ) t += it;
            else if ( isalpha(it) ) t += tolower(it);
        }
        int n = t.size();
        for ( int i = 0, j = n - 1; i < j; ++i, --j )
            if ( t[i] != t[j] ) return false;
        return true;
    }
};
/*
时间：0ms，击败：100.00%
内存：7.5MB，击败：58.65%
*/

法二：

非法字符直接跳过，只判断数字和英文字母。

class Solution {
public:
    bool valid( char ch ) {
        return isdigit( ch ) || isalpha( ch );
    }
    bool isPalindrome(string s) {
        int n = s.size();
        int i = 0, j = s.size() - 1;
        int k = 1 << 5;
        while ( i < j ) {
            while ( i < j && !valid(s[i]) ) ++i;
            while ( i < j && !valid(s[j]) ) --j;
            if ( s[i] != s[j] && s[i] != (s[j] ^ k) ) return false;
            ++i, --j;
        }
        return true;
    }
};
/*
时间：4ms，击败：93.73%
内存：7.2MB，击败：89.25%
*/