Leetcode.125.Valid Palindrome

题目

给定一个字符串, 判断字符串是否是回文, 只考虑字符和数字不考虑标点符号和特殊字符.

Input: "A man, a plan, a canal: Panama"
Output: true
Input: "race a car"
Output: false

思路

双指针, 一个从前向后移动, 一个从后向前移动, 当l >= r时即为回文.
时间复杂度O(n)
空间复杂度O(1)

bool isPalindrome(string s) {
    int n = (int)s.size();
    int l = 0, r = n - 1;
    while (l < r) {
        while (l < r && !isalnum(s[l])) {
            l++;
        }
        while (l < r && !isalnum(s[r])) {
            r--;
        }
        if (tolower(s[l]) != tolower(s[r])) {
            break;
        }
        l++;
        r--;
    }
    return l >= r;
}

总结

注意循环的边界问题, 嵌套循环容易造成无限循环.
熟悉string的API.

isalnum()：判断字符是否是字母或数字；
isalpha()：判断字符是否是字母；
iscntrl()：判断字符是否是控制字符；
isdigit()：判断字符是否是数字；
isgraph()：判断字符是否是可打印的非空格字符；
ispunct()：判断字符是否是标点符号；
isspace()：判断字符是否是空白字符；
isupper()：判断字符是否是大写字母；
isxdigit()：判断字符是否是十六进制数；
toupper()：转换为大写字母；
tolower()：转换为小写字母。