题目链接：Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,

“A man, a plan, a canal: Panama” is a palindrome.

“race a car” is not a palindrome.

Note:

Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

这道题的要求是判断字符串是否为回文，仅考虑数字和字母（忽略大小写），空串是回文。

思路比较简单，采用l和r两个指针，分布从左右往中间移动，跳过非数字字母的字符，比较若不同就返回false，直到相遇后返回true。注意一点就是忽略大小写，因此可以将大写字母转化成小写字母后再进行比较。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution
{
public:
    bool isPalindrome(string s)
    {
        int l = 0, r = s.size() - 1;
        while(l < r)
        {
            while(l < r && !isAlphanumeric(s[l]))
                ++ l;
            while(l < r && !isAlphanumeric(s[r]))
                -- r;
            if(s[l ++] != s[r --])
                return false;
        }
        return true;
    }
private:
    bool isAlphanumeric(char &c)
    {
        if(c >= 'A' && c <= 'Z')
            c += 32;
        return c >= 'a' && c <= 'z' || c >= '0' && c <= '9';
    }
};