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）。