【面试经典150 | 动态规划】最长回文子串

文章目录

写在前面
Tag
题目来源
解题方法
- 方法一：动态规划
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【动态规划】【字符串】

题目来源

5. 最长回文子串

解题方法

方法一：动态规划

动态规划方法主要参考官方题解，本题还有两种比较经典的方法，感兴趣的读者可以移步一文多图讲清楚解决最长回文子串问题的【中心扩展算法】与【Manacher算法】。

思路

对于一个字符串，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，仍是回文串。例如字符串 “ababa”，如果我们知道已知 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 ‘a’。

定义状态

根据这样的思路，我们可以使用动态规划的方法解决本题。我们使用 P(i, j) 表示字符串 s 的第 i 到 j 个字母组成的串（即字符串 s[i, ..., j]）是否为回文串，关于 P(i, j) 有以下两种情况：

P(i, j) = true，如果字符串 s[i, ..., j] 是回文串；
P(i, j) = false，其他情况下。

这里的「其他情况」包括：

s[i, ..., j] 本身不是一个回文串；
i > j，此时 s[i, ..., j] 不合法。

转移关系

根据以上分析有转移关系：

$KaTeX parse error: Expected 'EOF', got '&' at position 24: \dots = P(i+1, j-1) &̲ (s[i] == s[j])\dots$

base case

有一些边界条件：

如果字符串长度为 1，则一定是回文串，即 P(i, j) = true；
如果字符串长度为 2，则该字符串是否为回文串与字符串中两个字符是否一样有关，即 P(i, i+1) = (s[i] == s[i+1])。

最后返回

因为最后需要返回最长的回文子串，所以我们在更新 P(i, j) 的时候要记录取得最长回文子串的长度 maxLen 和起始字符 begin。最终返回 s.substr(begin, maxLen)。

实现代码

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) return s;

        int maxLen = 1, begin = 0;
    vector<vector<int>> dp(n, vector<int>(n));

    // 初始化所有长度为 1 的子串都是回文串
    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
    }

    // 开始递推，先枚举子串长度
    for (int L = 2; L <= n; ++L) {
        // 枚举左边界
        for (int i = 0; i < n; ++i) {
            int j = L + i - 1; // 右边界
            if (j >= n) break;

            if (s[i] != s[j]) {
                dp[i][j] = false;
            }
            else {
                if (j - i < 3) {
                    dp[i][j] = true;
                }
                else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }

            if (dp[i][j] && L > maxLen) {
                maxLen = L;
                begin = i;
            }
        }
    }
    return s.substr(begin, maxLen);
    }
};

复杂度分析

时间复杂度： $O(n^2)$ ， $n$ 是字符串的长度。