125. Valid Palindrome 验证回文串

@TOC

# 题目描述

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
``````

# 解题方法

# 列表生成式

python 处理起来很简单。isalnum()能判断字符是不是字母数字的，用列表表达式就能产生有效字符串，然后就可以看是不是回文。

``````class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
isValid = lambda x : x == x[::-1]
string = ''.join([x for x in s.lower() if x.isalnum()])
return isValid(string)
``````

# 正则表达式

``````class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.lower()
s = re.sub("\W", "", s)
N = len(s)
left, right = 0, N - 1
while left <= right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
``````

# 双指针

``````class Solution {
public:
bool isPalindrome(string s) {
int left = 0, right = s.size();
while (left <= right) {
if (!isalnum(s[left])) ++left;
else if (!isalnum(s[right])) --right;
else if ((s[left] + 32 - 'a') % 32 != (s[right] + 32 - 'a') % 32) return false;
else {
++left;
--right;
}
}
return true;
}
};
``````

# 日期

2018 年 2 月 4 日 2018 年 11 月 27 日 —— 最近的雾霾太可怕