传送门

给出一个英文句子，要求判断它是否是回文串。判断时忽略大小写、标点以及空格，同时空字符串视为回文串。

我的思路是O(n)扫过去清掉标点和空格并统一大小写，然后翻转字符串判断它与初始字符串是否相等。确实可以A但是时间复杂度惨不忍睹，感觉可以优化到O(1)，学习后会更新。

class Solution {
public:
    bool isPalindrome(string s) {
        string str = "";
        int n = s.size();

        for(int i = 0; i < n; i++)
            if(isalpha(s[i])) 
                str += tolower(s[i]);
            else 
                if(isdigit(s[i]))
                    str += s[i];

        string str1 = str;
        reverse(str1.begin(), str1.end());

        return str1 == str ? 1 : 0;
    }
};