题目描述

给定一个字符串，判断它是否是回文串。仅考虑大小写字母和数字，忽略其他字符。
规定空字符串也是回文串。在这道题目中，小写字母可以和大写字母匹配

样例

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

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

算法1

线性扫描 O(n)
双指针 主要的问题是去除字符段中除了字母,数字之外的内容,

C++ 代码

class Solution {
public:
    bool check(char c)
    {
        return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
    }

    bool isPalindrome(string s) {
        int i = 0, j = (int)s.size() - 1;
        while (i < j)
        {
            while (i < j && !check(s[i])) i ++ ;
            while (i < j && !check(s[j])) j -- ;
            if (s[i] != s[j] && s[i] != (s[j]^32)) return false;
            i ++, j --;
        }
        return true;
    }
};

算法2

vector容器,会占用较多的空间
reverse(beg,end)
reverse_copy(sourceBeg,sourceEnd,destBeg)

reverse()会将区间[beg,end)内的元素全部逆序；
reverse_copy()会将源区间[sourceBeg,sourceEnd)内的元素复制到”以destBeg起始的目标区间”，并在复制过程中颠倒安置次序；

C++ 代码

class Solution {
public:
    bool isPalindrome(string s) {
        vector<char> a;
        for(int i = 0; i < s.size(); i ++){
            if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= '0' && s[i] <= '9')) a.push_back(s[i]);
            if(s[i] >= 'A' && s[i] <= 'Z') a.push_back(s[i] - 'A' + 'a');
        }

        vector<char> b = a;
        reverse(a.begin(), a.end());
        if(a == b) return true;
        else return false;
    }
};