LeetCode#125 Valid Palindrome

原題連結

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

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

解法 1

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

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]只要其中一個碰到不合法的字元就跳過，只有兩個索引指向的字元合法時才進行比對：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

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 會不會比較快呢？

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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;     } };

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