#回文判斷 ## 題目描述 回文，英文palindrome，指一個順著讀和反過來讀都一樣的字符串，比如madam、我愛我，這樣的短句在智力性、趣味性和藝術性上都頗有特色，中國歷史上還有很多有趣的回文詩。 那么，我們的第一個問題就是：判斷一個字串是否是回文？ ## 分析與解法 回文判斷是一類典型的問題，尤其是與字符串結合后呈現出多姿多彩，在實際中使用也比較廣泛，而且也是面試題中的常客，所以本節就結合幾個典型的例子來體味下回文之趣。 ### 解法一 同時從字符串頭尾開始向中間掃描字串，如果所有字符都一樣，那么這個字串就是一個回文。采用這種方法的話，我們只需要維護頭部和尾部兩個掃描指針即可。 代碼如下：： ```cpp bool IsPalindrome(const char *s, int n) { // 非法輸入 if (s == NULL || n < 1) { return false; } const char* front,*back; // 初始化頭指針和尾指針 front = s; back = s+ n - 1; while (front < back) { if (*front != *back) { return false; } ++front; --back; } return true; } ``` 這是一個直白且效率不錯的實現，時間復雜度：O(n)，空間復雜度：O(1)。 ### 解法二 上述解法一從兩頭向中間掃描，那么是否還有其它辦法呢？我們可以先從中間開始、然后向兩邊擴展查看字符是否相等。參考代碼如下： ```cpp bool IsPalindrome2(const char *s, int n) { if (s == NULL || n < 1) { return false; } const char* first, *second; // m定位到字符串的中間位置 int m = ((n >> 1) - 1) >= 0 ? (n >> 1) - 1 : 0; first = s + m; second = s + n - 1 - m; while (first >= s) { if (*first!= *second) { return false; } --first; ++second; } return true; } ``` 時間復雜度：O(n)，空間復雜度：O(1)。 雖然本解法二的時空復雜度和解法一是一樣的，但很快我們會看到，在某些回文問題里面，這個方法有著自己的獨到之處，可以方便的解決一類問題。 ## 舉一反三 1、判斷一條單向鏈表是不是“回文” 分析：對于單鏈表結構，可以用兩個指針從兩端或者中間遍歷并判斷對應字符是否相等。但這里的關鍵就是如何朝兩個方向遍歷。由于單鏈表是單向的，所以要向兩個方向遍歷的話，可以采取經典的快慢指針的方法，即先位到鏈表的中間位置，再將鏈表的后半逆置，最后用兩個指針同時從鏈表頭部和中間開始同時遍歷并比較即可。 2、判斷一個棧是不是“回文” 分析：對于棧的話，只需要將字符串全部壓入棧，然后依次將各字符出棧，這樣得到的就是原字符串的逆置串，分別和原字符串各個字符比較，就可以判斷了。