125. Valid Palindrome

https://leetcode.com/problems/valid-palindrome/description/

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

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

Example 1:

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

Example 2:

Input: "race a car"
Output: false

Thoughts

忽略所有非数字和字母，检查给定str是否回文。要检查首尾配对是否相同，用首尾两个指针同时走，当遇到非数字和字母就让指针先走。

Code

/*
 * @lc app=leetcode id=125 lang=cpp
 *
 * [125] Valid Palindrome
 */

// @lc code=start
class Solution {
public:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.length() - 1; i < j;) {
            if (!isalpha(s[i]) && !isdigit(s[i])) {
                ++i;
            } else if (!isalpha(s[j]) && !isdigit(s[j])) {
                --j;
            } else {
                if (tolower(s[i]) != tolower(s[j])) {
                    return false;
                }
                ++i;
                --j;
            }
        }
        return true;
    }
};
// @lc code=end

class Solution {
    public boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            char cl = s.charAt(l);
            char cr = s.charAt(r);
            if (!Character.isLetterOrDigit(cl)) {
                l++;
            } else if (!Character.isLetterOrDigit(cr)) {
                r--;
            } else if (Character.toLowerCase(cl) == Character.toLowerCase(cr)) {
                l++;
                r--;
            } else {
                return false;
            }
        }

        return true;
    }
}

Analysis

Errors:

1. 把数字也当作需要忽略的字符了。

时间复杂度O(n).