# 125 - Valid Palindrome

解法一 - 做完前處理再比較

這題一開始的 idea 滿簡單的，就是先把大寫都轉成小寫，然後把非字母的 char 都移掉，再用兩個 pointer 分別從兩端向中間比較。

一開始的實作如下：

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty()) return true;

        // to lower case
        // https://stackoverflow.com/questions/313970/how-to-convert-stdstring-to-lower-case
        transform(s.begin(), s.end(), s.begin(), ::tolower);

        // remove other character
        // http://www.cplusplus.com/reference/cctype/isalnum/
        for(int i=0; i<s.length(); i++) {
            if(isalnum(s[i])) 
                continue;
            else {
                s.erase(i,1);
                if(i!=0) i -= 2;
                else i=0;
            }
        }

        // two pointer compare
        int begin=0, end=s.length()-1;

        while(begin<end) {
            if(s[begin] != s[end])
                return false;

            begin++;
            end--;
        }

        return true;
    }
};

寫題目過程中漏考慮到的 case:

1. "0P": 我題目沒有看清楚，alphanumeric 指的是字母跟數字的集合，所以0不能被移除掉。

2. "\"Stop!\" nine myriad murmur. \"Put up rum, rum, dairymen, in pots.\"": 一開始只寫了

            else {
                s.erase(i,1);
                i -= 2;
            }

可是如果 i == 0 時就有 char 被移除掉，那就會發生 i = -2 的情況，就會出問題，所以要改成：

            else {
                s.erase(i,1);
                if(i!=0) i -= 2;
                else i=0;
            }

1. "......a.....": 這個也是錯在 i 的變化，應該要長得像下面這樣

            else {
                s.erase(i,1);
                if(i!=0) i -= 2;
                else i=-1; // reset 下次 i 從 0 開始
            }

最後程式碼如下：

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty()) return true;

        // to lower case
        // https://stackoverflow.com/questions/313970/how-to-convert-stdstring-to-lower-case
        transform(s.begin(), s.end(), s.begin(), ::tolower);

        // remove other character
        // http://www.cplusplus.com/reference/cctype/isalnum/
        for(int i=0; i<s.length(); i++) {      
            if(isalnum(s[i])) 
                continue;
            else {
                s.erase(i,1);
                if(i!=0) i -= 2;
                else i=-1;
            }
        }

        // two pointer compare
        int begin=0, end=s.length()-1;

        while(begin<end) {
            if(s[begin] != s[end])
                return false;

            begin++;
            end--;
        }

        return true;
    }
};

以上這種寫法實在太醜了，而且效率超級低，時間複雜度 O(3n)： Runtime: 484 ms, faster than 5.17% of C++ online submissions for Valid Palindrome. Memory Usage: 9.3 MB, less than 60.81% of C++ online submissions for Valid Palindrome.

解法二 - 直接 Two Pointer

其實不需要全部先轉 lower case 跟移除非 alphanumeric 的 char：

class Solution {
public:
    bool isPalindrome(string s) {
        // Use 2 pointers to traverse from both side
        int l = 0, r = s.length()-1;

        // Check if s[l] == s[r] 
        while( l < r ) {
            while( l < s.length() && !isalnum(s[l]) ) {
                ++l;
            }

            while( r >= 0 && !isalnum(s[r]) ) {
                --r;
            }

            if( r < 0 or l >= s.length()) {
                break;
            }

            if( tolower(s[l]) != tolower(s[r]) ) {
                return false;
            }

            ++l;
            --r;
        }

        return true;
    }
};

上面這個做法雖然會過，但程式碼有點冗長，比較好的實作方法是：

class Solution {
public:
    bool isPalindrome(string s) {
        for(int i=0, j=s.length()-1; i<j; i++, j--) {
            while(isalnum(s[i])==false && i<j) i++; // Increment left ptr if not alphanumeric
            while(isalnum(s[j])==false && i<j) j--; // Decrement right ptr if not alphanumeric
            if(tolower(s[i]) != tolower(s[j]))
                return false;
        }

        return true;
    }
};

而且效率高多了：

Runtime: 4 ms, faster than 99.62% of C++ online submissions for Valid Palindrome. Memory Usage: 9.3 MB, less than 68.07% of C++ online submissions for Valid Palindrome.