# Valid Palindrome

## Question

### Problem Statement

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.

## 题解

### Python

class Solution:
# @param {string} s A string
# @return {boolean} Whether the string is a valid palindrome
def isPalindrome(self, s):
if not s:
return True

l, r = 0, len(s) - 1

while l < r:
# find left alphanumeric character
if not s[l].isalnum():
l += 1
continue
# find right alphanumeric character
if not s[r].isalnum():
r -= 1
continue
# case insensitive compare
if s[l].lower() == s[r].lower():
l += 1
r -= 1
else:
return False
#
return True


### C++

class Solution {
public:
/**
* @param s A string
* @return Whether the string is a valid palindrome
*/
bool isPalindrome(string& s) {
if (s.empty()) return true;

int l = 0, r = s.size() - 1;
while (l < r) {
// find left alphanumeric character
if (!isalnum(s[l])) {
++l;
continue;
}
// find right alphanumeric character
if (!isalnum(s[r])) {
--r;
continue;
}
// case insensitive compare
if (tolower(s[l]) == tolower(s[r])) {
++l;
--r;
} else {
return false;
}
}

return true;
}
};


### Java

public class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.trim().isEmpty()) {
return true;
}

int l = 0, r = s.length() - 1;
while (l < r) {
if(!Character.isLetterOrDigit(s.charAt(l))) {
l++;
continue;
}
if(!Character.isLetterOrDigit(s.charAt(r))) {
r--;
continue;
}
if (Character.toLowerCase(s.charAt(l)) == Character.toLowerCase(s.charAt(r))) {
l++;
r--;
} else {
return false;
}
}

return true;
}
}


### 源码分析

1. 找到最左边和最右边的第一个合法字符(字母或者字符)
2. 一致转换为小写进行比较