题目：
给定一个字符串，判断其是否为一个回文串。只包含字母和数字，忽略大小写。
样例
"A man, a plan, a canal: Panama" 是一个回文。
"race a car" 不是一个回文。
注意
你是否考虑过，字符串有可能是空字符串？这是面试过程中，面试官常常会问的问题。
在这个题目中，我们将空字符串判定为有效回文。
挑战
O(n) 时间复杂度，且不占用额外空间。
解题：
去除非有效字符后，整体是个回文串，两边查找，利用快速排序的思想，通过while找到有效的字符串
Java程序：
public class Solution {
/**
* @param s A string
* @return Whether the string is a valid palindrome
*/
public boolean isPalindrome(String s) {
// Write your code here
if(s.equals("")) return true;
int len = s.length();
int left = 0;
int right = len - 1;
s = s.toLowerCase();
while(left < right){
char leftchar = s.charAt( left );
char rightchar = s.charAt( right );
while(!isValid(leftchar)){
left ++;
leftchar = s.charAt( left );
if(left>=right) return true;
}
while(!isValid(rightchar)){
right --;
rightchar = s.charAt( right );
if(right<=left) return true;
}
if(leftchar != rightchar)
return false;
left ++;
right --;
}
return true;
}
public boolean isValid(char ch){
if(ch>='a' && ch <= 'z')
return true;
if(ch >='0' && ch <= '9')
return true;
return false;
}
}
总耗时: 14651 ms
Python程序：
class Solution:
# @param {string} s A string
# @return {boolean} Whether the string is a valid palindrome
def isPalindrome(self, s):
# Write your code here
if s.isspace() or s=="":
return True
s = s.lower()
left = 0
right = len(s) - 1
while left< right:
while (self.isValid(s[left]))==False:
left += 1
if left>= right:
return True
while (self.isValid(s[right])) ==False:
right -=1
if left>=right:
return True
if s[left]!= s[right]:
return False
left += 1
right -= 1 return True def isValid(self,ch): # isalnum()
if ch.isalpha():
return True
if ch.isdigit():
return True
return False
总耗时: 825 ms