Description
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Answer
One of the most important feature of palindrome is adding the same character or string at the head and end of a palindrome will not make the original string not a palindrome. So we can start from the middle of the given string and use two pointers to expand the string. If we can get the whole string through expansion, then it is a palindrome and return true. If not, then return false.
Code
C++
class Solution {
public:
bool isPalindrome(string s) {
for(int i = s.length() - 1; i >= 0; --i)
{
if(!(s[i] >= 65 && s[i] <= 90 || s[i] >= 97 && s[i] <= 122 || s[i] >= 48 && s[i] <= 57))
s.erase(i, 1);
if(s[i] >= 65 && s[i] <= 90)
s[i] += 32;
}
if(s.length() <= 1) return true;
int n = s.length();
if(n % 2)
{
for(int i = 1; i <= n / 2; ++i)
{
if(s[n / 2 + i] == s[n / 2 - i]) continue;
else return false;
}
return true;
}
else
{
if(s[n / 2] != s[n / 2 - 1]) return false;
for(int i = 0; i < n / 2; ++i)
{
if(s[n / 2 + i] == s[n / 2 - i - 1]) continue;
else return false;
}
return true;
}
}
};
