leetcode解题: Valid Palindrome (125)

发表于 | 分类于

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.

Show Company Tags
Show Tags
Show Similar Problems

解法1： Two pointers, O(N)

用双指针很简单。要注意的是要跳过非alphanumeric的数字，这里C++里面判断是否是alphanumeric的数字的时候是用的isalnum（x)。 转化为lowercase的时候用的是tolower（x)
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isPalindrome(string s) {
        if (s.empty()) {
            return true;
        }
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < j && !isalnum(s[i])) { ++i;}
            while (i < j && !isalnum(s[j])) { --j;}
            if (i < j) {
                if (tolower(s[i]) != tolower(s[j])) {
                    return false;
                } else {
                    ++i;
                    --j;
                }
            }
        }
        
        return true;
    }
};

Java

1