3.3 回文字符串

回文是一類特殊的字符串。不管是從頭到尾讀取一個回文，還是顛倒過來從尾到頭讀取一個回文，得到的內容是一樣的。英語中有很多回文單詞，如"noon"和"madam"等。如果不考慮字符串中的空格和標點符號，并且忽略字母大小寫的不同，那么還有更多有意思的回文，如"Sir，I demand，I am a maid named Iris."和"Bob：Did Anna peep？Anna：Did Bob？"等。

中文博大精深，自然也有很多有趣的回文，如有回文對聯"上海自來水來自海上"和"黃山落葉松葉落山黃"等。如果不考慮標點符號，中文還有"我為人人，人人為我"等經典回文。

回文是一種大家喜聞樂見的文字游戲，與回文相關的非常有意思的面試題也有很多。除了本章幾道典型的與回文有關的面試題，在第13章和第14章中也有與回文有關的題目。下面從判斷一個字符串是不是回文開始介紹。

面試題18：有效的回文

分析：判斷一個字符串是不是回文，常用的方法就是使用雙指針。可以定義兩個指針，一個指針從第1個字符開始從前向后移動，另一個指針從最后一個字符開始從后向前移動。如果兩個指針指向的字符相同，則同時移動這兩個指針以判斷它們指向的下一個字符是否相同。這樣一直移動下去，直到兩個指針相遇。

由于題目要求只考慮字母和數字字符，如果某個指針指向的字符既不是字母也不是數字，則移動指針跳過該字符。同時，由于題目要求忽略大小寫，因此需要把所有的字母都轉化成小寫形式（或大寫形式）再做比較。

以下是Java的參考代碼：

在上述代碼中，兩個變量i和j相當于兩個指針。由于兩個指針移動的總次數最多等于字符串的長度，因此該解法的時間復雜度是O（n）。

面試題19：最多刪除一個字符得到回文

分析：和面試題18類似，本題還是從字符串的兩端開始向里逐步比較兩個字符是不是相同。如果相同，則繼續向里移動指針比較里面的兩個字符。如果不相同，按照題目的要求，在刪除一個字符之后再比較其他的字符就能夠形成一個回文。由于事先不知道應該刪除兩個不同字符中的哪一個，因此兩個字符都可以進行嘗試。這種思路對應的Java的參考代碼如下所示：

在函數validPalindrome的最后的return語句中，如果變量start等于輸入字符串s的長度的一半，那么字符串s本身就是一個回文。如果變量start小于字符串s的長度的一半，那么下標為start和end的兩個字符不相同，分別跳過下標start和end（相當于刪除字符串中下標為start或end的字符），調用函數isPalindrome可以判斷剩下的字符串是不是一個回文。

面試題20：回文子字符串的個數

分析：前面都是從字符串的兩端開始向里移動指針來判斷字符串是否是一個回文，其實也可以換一個方向從字符串的中心開始向兩端延伸。如果存在一個長度為m的回文子字符串，則分別再向該回文的兩端延伸一個字符，并判斷回文前后的字符是否相同。如果相同，就找到了一個長度為m+2的回文子字符串。例如，在字符串"abcba"中，從中間的"c"出發向兩端延伸一個字符，由于"c"前后都是字符'b'，因此找到了一個長度為3的回文子字符串"bcb"。然后向兩端延伸一個字符，由于"bcb"的前后都是字符'a'，因此又找到一個長度為5的回文子字符串"abcba"。

值得注意的是，回文的長度既可以是奇數，也可以是偶數。長度為奇數的回文的對稱中心只有一個字符，而長度為偶數的回文的對稱中心有兩個字符。

基于這種思路可以編寫出如下所示的代碼：

字符串的下標為i。第i個字符本身可以成為長度為奇數的回文子字符串的對稱中心，同時第i個字符和第i+1個字符可以一起成為長度為偶數的回文子字符串的對稱中心。因此，在上述代碼中，for循環通過對每個下標i調用兩次countPalindrome來統計回文子字符串的個數。

上述解法仍然需要兩個嵌套的循環，因此時間復雜度是O（n²）。該解法只用到了若干變量，其空間復雜度是O（1）。