LeetCode第125题解析

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

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

示例 1:

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

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

1. islower(char c) 是否为小写字母
2. isupper(char c) 是否为大写字母
3. isdigit(char c) 是否为数字
4. isalpha(char c) 是否为字母
5. isalnum(char c) 是否为字母或者数字
6. toupper(char c) 字母小转大
7. tolower(char c) 字母大转小
8. 大小写字母的ASCII码值：a-z:97-122；A-Z:65-90。相差32。

第一种方法：先将字符串处理成有效字符串，包括删除数字和字母以外的字符，并且转换成统一的大小写。在利用rbegin、rend逆序输出字符串（string tmp(s.rbeing( ), s.rend( ))），最后进行比较即可。

class Solution {
public:
    bool isPalindrome(string s) {
        string tmp;
        //处理字符串
        for (char c : s) {
            if (isalnum(c)) {
                tmp += tolower(c);
            }
        }
        //比较处理后的字符串是否是回文串
        //逆序输出后进行比较
        string tmp1(tmp.rbegin(), tmp.rend());
        return tmp == tmp1;
    }
};

第二种方法：双指针法。可以处理字符串后进行双指针法，也可以指针在原字符串上进行双指针法。

class Solution {
public:
    bool isPalindrome(string s) {
        string tmp;
        //处理字符串
        for (char c : s) {
            if (isalnum(c)) {
                tmp += tolower(c);
            }
        }
        //比较处理后的字符串是否是回文串
        //利用双指针法
        int i = 0;
        int j = tmp.size() - 1;
        for ( ; i < j; ++i) {
            if (tmp[i] != tmp[j])
                return false;
            j--;
        }
        return true;
    }
};

直接在原字符串上利用双指针法：

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0;
        int right = s.size() - 1;
        while(left < right) {
            while (left < right && !isalnum(s[left])) {
                left++;
            }

            while (left < right && !isalnum(s[right])) {
                right--;
            }

            if (tolower(s[left]) != tolower(s[right]))
                return false;
            left++;
            right--;
        }
        return true;
    }
};