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.
验证一个给定的字符串是否为回文,用两个指针分别指向字符的首尾,判断是否相同,相同就的都向中间移动1位,判断下一组,左指针小于右指针就一直循环。遇到标点符号就跳过,处理下一个。遇到大写字母就转换成小写字母。
Java:
class Solution {
public boolean isPalindrome(String s) {
char[] chs = s.toCharArray();
int left = 0, right = s.length() - 1;
while (left <= right) {
while (left < right && !Character.isLetterOrDigit(chs[left]))
left++;
while (left < right && !Character.isLetterOrDigit(chs[right]))
right--;
if (Character.toLowerCase(chs[left++]) != Character.toLowerCase(chs[right--]))
return false;
}
return true;
}
}
Java:
public class Solution {
public boolean isPalindrome(String s) {
int size = s.length(), i = 0, j = size - 1;
s = s.toLowerCase(); while (i < j) {
if (!(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') && !(s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
i++;
}
else if (!(s.charAt(j) >= 'a' && s.charAt(j) <= 'z') && !(s.charAt(j) >= '0' && s.charAt(j) <= '9')) {
j--;
}
else {
if (s.charAt(i) != s.charAt(j)) return false; i++;
j--;
}
}
return true;
}
}
Python:
class Solution:
def isPalindrome(self, s):
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i, j = i + 1, j - 1
return True
C++:
class Solution {
public:
bool isPalindrome(string s) {
int left = 0, right = s.size() - 1 ;
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;
}
};
C++:
class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = s.size() - 1;
while(l <= r){
while(!isalnum(s[l]) && l < r) l++;
while(!isalnum(s[r]) && l < r) r--;
if(toupper(s[l]) != toupper(s[r])) return false;
l++, r--;
}
return true;
}
};
类似题目:
[LeetCode] 9. Palindrome Number 验证回文数字
[LeetCode] 5. Longest Palindromic Substring 最长回文子串
[LeetCode] 516. Longest Palindromic Subsequence 最长回文子序列
All LeetCode Questions List 题目汇总