【leetcode】125. 验证回文串

题目

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

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

思路

1. 筛选：遍历字符串进行一次遍历，保留字母和数字字符，放在另一个字符串中。注意大小写字母的转换
2. 使用双指针：初始时，左右指针分别指向字符串的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明是回文串。

代码

class Solution {
public:
    bool isPalindrome(string s) {
        string ss = "";
        for(int i=0; i<s.length(); i++){
            char ch = s[i];
            if( (ch>='0'&&ch<='9') || (ch>='a'&&ch<='z') ){
                ss += ch;
            }else if (ch>='A'&&ch<='Z') {
                int diff = (int)('A'-'a');
                // cout << diff << endl;
                ch = (char)(ch-diff);
                ss += ch;
            }
        }
        cout << ss << endl;
        int i=0, j=ss.length()-1;
        while( i < j ){
            if( ss[i]!=ss[j] ){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
};

复杂度

参考

官方题解