Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Notice
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.
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Challenge
O(n) time without extra memory.
LeetCode上的原题，请参见我之前的博客Valid Palindrome。
解法一：
class Solution { public: /** * @param s A string * @return Whether the string is a valid palindrome */ 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; } bool isAlNum(char c) { if (c >= 'a' && c <= 'z') return true; if (c >= 'A' && c <= 'Z') return true; if (c >= '0' && c <= '9') return true; return false; } };
解法二：
class Solution { public: /** * @param s A string * @return Whether the string is a valid palindrome */ 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; } };
本文转自博客园Grandyang的博客，原文链接：验证回文字符串[LintCode] Valid Palindrome ，如需转载请自行联系原博主。
