【leetcode】5.最长回文子串

leetcode刷题笔记-5.最长回文子串。这么经典的题目我竟然现在才刷，懒虫一个。

参考：https://writings.sh/post/algorithm-longest-palindromic-substring

题目

https://leetcode.cn/problems/longest-palindromic-substring/description/

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

回文字符串：从前往后和从后往前读的结果完全一致，比如aba；

子串：字符串s中的一部分称之为子串。与之区别的是子序列，子序列是不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

提示：

1 2	1 <= s.length <= 1000 s 仅由数字和英文字母组成

思路一：暴力 O(N^3)

基本代码

最蠢的办法就是直接暴力了，一个函数判断是否是回文，再用双层循环来枚举所有子串

class Solution {
    bool isReverseString(const string& s, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

public:
    string longestPalindrome(string s) {
        if(s.size()<=1){
            return s;
        }
        // 一个也算回文
        int maxLength = 1;
        string ret;
        ret.push_back(s[0]);
        // 再去找其他的
        for (int i = 0; i < s.size() - 1; i++) {
            for (int j = i + 1; j < s.size(); j++) {
                if (isReverseString(s, i, j)) {
                    int len = j - i + 1;
                    // cout << len << endl;
                    if (len > maxLength) {
                        maxLength = len;
                        ret = s.substr(i, len);
                        // cout << len << endl;
                    }
                }
            }
        }
        return ret;
    }
};

对于本题而言，也能通过，但很明显耗时太长了，这是一个O(N^3)时间复杂度的暴力算法。

一定优化

其实这个暴力求解法也有可优化的地方，即内层循环的枚举我们可以用maxLength进行枚举，j的初始值是i+maxLength，这样每一次枚举都是比上一次更长的字符串，得到回文子串后也不需要判断长度是否大于maxLength了，能减少很多次遍历。

且在当前的写法中，每次得到一个结果，我们都调用了一次substr函数，这个函数也是O(N)的时间复杂度。

1	ret = s.substr(i, len);

我们可以将其改成记录结果字符串的起始下标和长度，在最终才调用substr函数来构造返回字符串，这样也能减少一定的时间复杂度。

优化后的代码如下，注意maxLength必须初始化为1。

class Solution {
    bool isReverseString(const string& s, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

public:
    string longestPalindrome(string s) {
        if (s.size() <= 1) {
            return s;
        }
        // 一个也算回文
        int maxLength = 1;
        int begin = 0,length = 1;
        // 再去找其他的
        for (int i = 0; i < s.size() - 1; i++) {
            for (int j = i + maxLength; j < s.size(); j++) {
                if (isReverseString(s, i, j)) {
                    int len = j - i + 1;
                    maxLength = len;
                    begin = i;
                    length = len;
                }
            }
        }
        // 最后才构造结果字符串
        return s.substr(begin,length);
    }
};

多次提交测试，平均耗时都是之前1000ms的十分之一了，还是有不少提升的，但是时间复杂度依旧不变，还是O(N^3)。

思路二：动态规划 O(N^2)

二维数组

首先我们要知道，如果一个字符串是回文子串，那么它的中间一部分也一定是个回文子串。比如ABCBA的中间部分BCB也是一个回文子串。

这样我们就可以得出一个二维的dp数组，数组的下标(i,j)代表s字符串中，从i到j的这个字符串是一个回文子串。且i大于j的情况是不合法的。

这样我们就能省去很多的判断步骤，如果dp[i][j]=true，那么只需要判断i-1和j+1是否相等，就可以知道(i-1,j+1)这个范围是不是一个回文子串了。递推公式如下

1	dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])

那么dp数组要怎么遍历呢？从递归公式中可知，当前状态i,j依赖于i+1,j-1，即依赖于当前元素右上角的哪一个。所以，我们需要先遍历列j，再遍历行i。

在别的题解中你可能看到大家谈论的是左下角，这是因为矩阵的坐标系原点选择不同，我个人比较喜欢选左上角作为原点，然后往左是i下标，往下是j下标。

由下图可知，当我们需要知道(1,2)这个下标位置的结果是多少的时候，我们需要先把(0,3)给搞出来，所以应该让j作为外层循环开始遍历，这样才能保证遍历到某一个位置的时候，依赖项已经更新完成了。

继续确定dp数组的初始值，我们可以知道长度为1的时候肯定是个回文子串，即所有i和j相等的位置都可以初始化为true。长度为2的时候是否为子串需要进行判断，两个字符相同就是个回文子串。

现在就可以写代码了

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) {
            return s;
        }
        // 初始dp数组，[i][j]代表下标i到j是回文串
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        // 一个字符的时候肯定是true
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 记录结果字符的起始位置
        int maxLength = 1;
        int begin = 0;
        // 需要先遍历列j在遍历行i
        for (int j = 0; j < n; j++) {
            // i大于j的情况不合法
            for (int i = 0; i < j; i++) {
                // 两个字符相等是回文
                if (j == i + 1 && s[i] == s[j]) {
                    dp[i][j] = true;
                }
                // 依赖于右上角，注意i+1不能超过j-1
                else if (i + 1 <= j - 1 && dp[i + 1][j - 1] == true &&
                         s[i] == s[j]) {
                    dp[i][j] = true;
                }
                // 当前是回文，更新最大值
                if (dp[i][j] == true && maxLength < j - i + 1) {
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLength);
    }
};

代码的时间复杂度和空间复杂度都是O(N^2)。

建议根据代码的遍历顺序画个矩阵，更方便理解。

一维数组

使用一维数组，就可以降低一层空间复杂度。对应的思路也需要改变。

数组中dp[j]的值是下标j和j之前的最大回文子串的起始下标i；
易得初始值dp[0] = 0；

举例字符串aabba对应的dp数组，第一个a的最大回文子串起始地址是他自己，也就是0；第二个a之前的最大回文子串是aa，所以起始地址是0；第三个b之前的最大回文子串是它自己，因为aab不构成回文子串；第四个b之前的最大回文子串是bb，起始地址下标是2；最后一个a的最大回文子串是abba，起始下标是1。

1 2	a a b b a 0 0 2 2 1

另外我们需要知道每一位的递推值是怎么的来的。依照上面这个dp数组，假设我们需要递推最后一位a（下标为4）的dp值，那么应该是前一位b（下标为3）的最长子串起始下标的前一位是否和当前位相等，即判断s[i]==s[dp[i-1]-1]。

如果二者相等，则说明这个回文子串还可以被扩展，此时dp[i]等于dp[i-1]-1，子串长度是i-(dp[i-1]-1)+1。对于当前这个例子，dp[4]=1，回文子串长度是4-1+1=4。

这里还有另外一个结论，即当前位i组成的最长回文子串长度一定只会比i-1能组成的最长回文子串长度多两个字符（即i-1能组成的最长回文子串左右各多一个字符）。

如果不相等，说明前一位的回文子串不能被扩展，但这并不代表当前位并不能组成回文子串了。如下图所示，虽然当前j和前一位j-1的回文子串不能继续扩展，但它依旧有一个长度为3的回文子串。这时候就需要从j之前通过遍历来判断是否有回文子串了。

不过我们并不需要从0开始遍历，只需要从dp[j-1]开始遍历就可以了（即上图中下标为3的字母c开始）。前文说了，当前位i组成的最长回文子串长度一定只会比i-1能组成的最长回文子串长度多两个字符，不可能会有dp[j-1]-1之前到j能组成的回文串，而(dp[j-1]-1,j)这个子串我们已经在前面的条件中判断过不是回文了。

思路解决了，就可以写代码了

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) {
            return s;
        }
        vector<int> dp(n, 0);
        dp[0] = 0; // 下标为0只能和自己组成回文串
        int maxLength = 1;
        int begin = 0;
        // 注意j要从1开始，因为0已经被初始化过了，而且我们需要访问j-1
        for (int j = 1; j < n; j++) {
            if (dp[j - 1] - 1 >= 0 && s[j] == s[dp[j - 1] - 1]) {
                dp[j] = dp[j - 1] - 1;
            } else {
                // 从左向右找
                int left = dp[j - 1];
                int right = j;
                int start = left; // 记录回文子串查找的起始位置
                // 开始遍历
                while (left < right) {
                    // 二者不相等，不是回文，左侧需要缩限
                    if (s[left] != s[right]) {
                        right = j;        // 重置right
                        start = left + 1; // 左侧缩限
                    } else {
                        // 是回文，右侧缩限
                        right--;
                    }
                    // 不管是不是回文，左侧都需要缩限
                    left++;
                }
                dp[j] = start;
            }
            // 更新最大长度
            int len = j - dp[j] + 1;
            if (len > maxLength) {
                maxLength = len;
                begin = dp[j];
            }
        }
        return s.substr(begin, maxLength);
    }
};

虽然这么做的时间复杂度依旧是O(N^2)，但是空间复杂度被降为了O(N)。

思路三：中心扩散 O(N^2)

中心扩散的思路比较简单，遍历每一个下标，从这个下标开始往左往右扩散，直到找到最长的回文子串。这个思路不需要借助额外的数组，空间复杂度为O(1)。时间复杂度依旧是O(N^2)。

第一版本代码如下

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) {
            return s;
        }
        int maxLength = 1;
        int maxBegin = 0;
        for (int i = 0; i < n; i++) {
            int left = i - 1, right = i + 1;
            // 扩展
            int len = 1;
            int begin = i;
            while (left >= 0 && right < n) {
                if (s[left] != s[right]) {
                    break;
                }
                // 相同，记录长度和开始下标
                len = right - left + 1;
                begin = left;
                // 扩展
                left--;
                right++;
            }
            // 更新最大长度
            if (len > maxLength) {
                maxLength = len;
                maxBegin = begin;
            }
        }
        // 返回结果
        return s.substr(maxBegin, maxLength);
    }
};

这个代码看上去好像没有问题，但实际上我们漏掉了回文串为偶数的情况，直接从长度为3的回文串开始递推了。这是不可行的。

应该要把回文串长度为奇数，回文串长度为偶数的情况都考虑进去。下面是修改后的代码，其中使用了C++17的新特性，auto的结构化绑定来接收pair返回值，会方便一些。

class Solution {
    // 从left和right开始往左右扩展找回文子串，返回值是起始下标和长度
    pair<int, int> findReverseString(const string& s, int left, int right) {
        // 记录
        int len = 1;
        int begin = left;
        // 往两边扩展
        while (left >= 0 && right < s.size()) {
            if (s[left] != s[right]) {
                break;
            }
            // 相同，记录长度和开始下标
            len = right - left + 1;
            begin = left;
            // 扩展
            left--;
            right++;
        }
        return {begin, len};
    }

public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1) {
            return s;
        }
        int maxLength = 1;
        int maxBegin = 0;
        for (int i = 0; i < n; i++) {
            // 偶数情况
            auto [begin, len] = findReverseString(s, i, i + 1);
            // 奇数情况
            auto [begin2, len2] = findReverseString(s, i - 1, i + 1);
            // 如果奇数的结果更长，更新结果
            if (len2 > len) {
                len = len2;
                begin = begin2;
            }
            // 更新最大值
            if (len > maxLength) {
                maxLength = len;
                maxBegin = begin;
            }
        }
        // 返回结果
        return s.substr(maxBegin, maxLength);
    }
};