5.最长回文子串

中等题

回文就是从前往后和从后往前写都是一样的。从这个定义出发，可以有两种判断回文的方式：

1. 将一个字符串和其逆序比较，完全相同就是回文。
2. 选择字符串中间位置的字符，向两边扩散，每次各读入一个字符。如果两边同时结束并且读到的字符都分别相同，就是回文。

同以前一样，本文仍会展示一些可能的想法和思路，无论最终能否通过OJ。

思路一

由判断方式1很容易想出的暴力思路。找到所有的字符串组合，并且判断是否是回文。可以把字符串切割看成首尾两个指针的运动，因此找到所有可能的字符串组合需要一个O(n²)的复杂度（两层循环）。每找到一个可能的字符串就要判断是否是回文，将一个字符串逆序又需要n的复杂度。总的复杂度达到O(n³)，对于算法应该来说不算是个好消息。我们当然可以做一些所求条件的简化，例如从最长的字符串开始，但仍然无法改变复杂度的阶数。代码如下，无法通过力扣OJ。

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        int len = size+1;
        while(len--){
            for(int i=0,j=len-1;j<=size-1;){
                if(isPalindrome(s.substr(i,len))) return s.substr(i,len);
                else{
                    i++;
                    j++;
                }
            }
        }
        return s.substr(0);
    }

    bool isPalindrome(string s){
        for(int i=0; i<(s.size()+1)/2;i++){
            if(s.substr(i,1) != s.substr(s.size()-1-i,1)) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路二

采用判断方法2的中心扩散法。该方法中，需要寻找到所有可能的字符串中心，然后对其往两侧进行同步扩散比对。需要注意的是，回文数的中心有两种可能，即任意单字符或两个相同的字符。寻找所有可能的中心只需要一层循环。对于每个中心，扩散比对也只需要一层循环，总时间复杂度为O(n²)。代码如下：

string longestPalindrome(string s){
        string res = s.substr(0,1); //默认就取第一个字符好了
        for(int i=0; i<s.size(); i++ ){
            string cur = expandCenter(s,i,i); //中心是一个字符的扩展
            if(cur.size() > res.size()) res = cur;
        }
        for(int i=0; i<s.size()-1; i++){
        	//这个循环其实可以合并到上面一个循环，因为下标越界在expandCenter函数中会被自动排除。不过这不影响复杂度。
            if(s.substr(i,1) == s.substr(i+1,1)){
                string cur = expandCenter(s,i,i+1); //中心是两个字符的扩展
                if(cur.size() > res.size()) res = cur;
            }
        }
        return res;
    }

//返回的是某个中心的最大回文
string expandCenter(const string& s, int left, int right){
		//中心扩展。只有下标不越界、并且保证回文性质的才继续扩展
        while(left>=0 && right<s.size() && s[left] == s[right]){
            left--;
            right++;
        }
        return s.substr(left+1,right-left-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
25

这样在力扣的OJ上是可以通过的，用时24ms。还有线性复杂度的manacher算法没有了解。

总结

• 对算法的事先复杂度判断很重要
• 函数的运算尽可能都以int、double这样的数量作为参数、返回值等，我这里参数用了int，返回值使用的是string，其实可以统一成int型变量以表示下标，到最后再根据下标取出子串。