LeetCode#125 Valid Palindrome

原題連結

所謂 Palindrome 就是迴文，也就是那些倒過來看還是一樣的文字，例如 aabaa。

單純的迴文太容易了，只要用兩個索引或指標左右逼近即可。leetcode 當然要加點料，否則本題就變成送分題了。解題系統會在測試數據插入空白，標點符號，字元大小寫也不固定。

解法 1

此解法相信大多數人都想得到，先對原來的輸入走訪一圈，用一個新字串儲存過濾後的結果(按照題意，僅需要儲存英文字母與數字)，然後對這個新字串做檢測即可：

class Solution{
public:
    bool isPalindrome(string s) {
        if(s.empty())
            return true;
        
        string tmp;
        for(int i = 0; i < s.size(); ++i){
            if(isalpha(s[i]))
                tmp.push_back(tolower(s[i]));
            else if(isdigit(s[i]))
                tmp.push_back(s[i]);
        }
            
        int left = 0;
        int right = tmp.size() - 1;
        while(left < right){
            if(tmp[left++] != tmp[right--])
                return false;
        }
        
        return true;
    }
};

然而，這樣只有第三名的水準：

解法 2

如果改用指標指向合法的字元如何？

class Solution{
public:
    bool isPalindrome(string s) {
        if(s.empty())
            return true;
        
        vector<char*> tmp;
        for(int i = 0; i < s.size(); ++i){
            if(isalpha(s[i])){
                s[i] = tolower(s[i]);
                tmp.push_back(&s[i]);
            }else if(isdigit(s[i])){
                tmp.push_back(&s[i]);
            }
        }
            
        int left = 0;
        int right = tmp.size() - 1;
        while(left < right){
            if(*tmp[left++] != *tmp[right--])
                return false;
        }
        
        return true;
    }
};

結果更慘，掉到第四名去了：

解法 3

小弟資質愚魯，想不出更好的解法了，只好來偷看別人的解答，下方的解答參考自靈魂機器，這個解法的特色是不需要額外的記憶體空間，只使用兩個索引[left, right]從左右逼近。思路是既然我們只對合法的字元有興趣，那[left, right]只要其中一個碰到不合法的字元就跳過，只有兩個索引指向的字元合法時才進行比對：

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty())
            return true;
        
        for(int i = 0; i < s.size(); ++i){
            if(isalpha(s[i]))
                s[i] = tolower(s[i]);
        }
            
        int left = 0;
        int right = s.size() - 1;
        while(left < right){
            if(!isalnum(s[left])){
                ++left;
            }else if(!isalnum(s[right])){
                --right;
            }else{
                if(s[left] != s[right])
                    return false;
                ++left;
                --right;
            }
        }
        
        return true;
    }
};

悲劇了，這次掉到第六名：

這是為何呢？因為筆者做了點小改動，第一個迴圈原本的作法是用 std::transform，我改用了手寫迴圈，如果改回  transform(s.begin(), s.end(), s.begin(), ::tolower) 就拿到了第二名，也可以從此看出為何 Effective STL 建議不要使用手寫迴圈，STL 的優化能力居然超過手寫迴圈！

解法 4

第一名是怎麼辦到的？筆者想到的是如果拿掉 std::transform 會不會比較快呢？

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty())
            return true;
        
        int left = 0;
        int right = s.size() - 1;
        while(left < right){
            if(!isalnum(s[left])){
                ++left;
            }else if(!isalnum(s[right])){
                --right;
            }else{
                if(tolower(s[left]) != tolower(s[right]))
                    return false;
                ++left;
                --right;
            }
        }
        
        return true;
    }
};

很遺憾的是，這樣仍然只有第二名，第一名到底用了什麼神奇演算法呢？若哪位朋友知道請提供一下，感恩~