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 };        //該數(shù)組0~25對應(yīng)a~z，26~51對應(yīng)A~Z，52~61對應(yīng)'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);  //若字符串為奇數(shù)，去掉中間那個
        }
        for (i = 0; i<v1.size(); i++) {                //對字符串中字符出現(xiàn)的位置索引進(jìn)行累加，累加的和存入數(shù)組
            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++) {                        //每個字符(此處大小寫合并)的索引的和必然是（容器大小加一）的整數(shù)倍
            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;
    }
};

原文地址：我的主頁文章