Question
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Example
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.
Solution
First solution
First I figure out an complex solution, the core idea in this algorithm is that the index of characters from both sides of the string should add up to a certain figure, which is the size of that string plus one.
class Solution {
public:
static bool isPalindrome(string s) {
int i = 0;
vector<char> v1(0);
unsigned int sum[62] = { 0 }; //该数组0~25对应a~z，26~51对应A~Z，52~61对应'0'~'9'
for (; i<s.length(); i++) {
if ((s[i] >= 'a'&&s[i] <= 'z') || (s[i] >= 'A'&&s[i] <= 'Z')||(s[i] >= '0'&&s[i] <= '9')) { //去掉各种cases存入容器中
v1.push_back(s[i]);
}
}
if ((int)v1.size() % 2 == 1) {
v1.erase(v1.begin() + (v1.size() - 1) / 2); //若字符串为奇数，去掉中间那个
}
for (i = 0; i<v1.size(); i++) { //对字符串中字符出现的位置索引进行累加，累加的和存入数组
if(v1[i]>='a'&&v1[i]<='z')
sum[v1[i] - 'a'] += i + 1;
else if(v1[i] >= 'A'&&v1[i] <= 'Z') sum[v1[i] - 'A' + 26] += i + 1;
else sum[v1[i] - '0' + 52] += i + 1;
}
for (i = 0; i<26; i++) { //每个字符(此处大小写合并)的索引的和必然是（容器大小加一）的整数倍
if ((sum[i] + sum[i + 26]) % (v1.size() + 1) != 0) return false;
}
for (i = 52; i < 62; i++) {
if (sum[i] % (v1.size() + 1) != 0) return false;
}
return true;
}
};
Second solution
when I look up the handbook, it provide a much simpler solution.
O(n) runtime, O(1) space:
The idea is simple, have two pointers – one at the head while the other one at the tail.
Move them towards each other until they meet while skipping non-alphanumeric characters.
I implement it in C++(I really should have thought of this method =_=)
class Solution {
public:
static bool isPalindrome(string s) {
int i=0,j=s.length()-1;
while(i<j){
while(i<j&&!isdigit(s[i])&&!isalpha(s[i])) i++;
while(i<j&&!isdigit(s[j])&&!isalpha(s[j])) j--;
if(tolower(s[i])!=tolower(s[j])) return false;
i++;
j--;
}
return true;
}
};
