[C++知识库]2021.8.18 力扣-最长回文子串

题目描述：

给你一个字符串?s，找到?s?中最长的回文子串。

方法一：

class Solution {
public:
    string longestPalindrome(string s) {
        int maxlen = 0;
        int star = 0;   //回文子串的开始下标
        int templen1, templen2, templen;
        for (int i = 0; i < s.size(); i++)
        {
            templen1 = expandAroundCenter(s, i, i);     //以一个字符为中心扩展
            templen2 = expandAroundCenter(s, i, i + 1); //以两个字符为中心扩展
            templen = max(templen1, templen2);
            if (templen > maxlen)
            {
                maxlen = templen;
                star = i - (templen - 1) / 2;
            }
        }
        return s.substr(star,maxlen);
        //substr()函数的作用：截取复制出字符串中的一段，第一个参数是起始指针，第二个参数是截取长度
    }
    int expandAroundCenter(string& s, int left, int right)
    //以下标为i和j的字符作为中心，开始扩展，计算得到的回文子串的长度
    {
        while (left >= 0 && right < s.size() && s[left] == s[right])
        {
            left--;
            right++;
        }
        return right - left - 1;
    }
};

一开始的思路只有暴力法，就是用两次的for循环加reverse()函数判断是否是回文子串，本以为这样做的时间复杂度是O(n2)，结果最后会超时，原来是因为reverse()函数本身的时间复杂度就是O(n)，导致最终算法的时间复杂度是O(n3)，所以暴力法还是不行。

查看了题解，最后用了中心扩展法，即每次遍历时选中一个字符或者两个字符作为回文子串的中心，然后同时向左和右扩展查找最长的回文子串。例如cac就是以a为回文子串的中心，caac就是以aa为回文子串的中心，于是总共要判断2n+1次(一个字符的为n次，两个字符的为n-1次)，每次判断时最多扩展n/2次，所以算法的时间复杂度为O(n2)。

本道题中，在expandAroundCenter(string& s, int left, int right)函数中，若把string& s的引用符号&去掉，则执行时间将会大大增多，原因：c++中参数是按值传递，如果不使用引用或者指针，则这个地方每一次函数调用，string就会被复制一次，效率很低，使用引用的话函数传递的是string的引用，不会导致复制。