动态规划——最长回文子串_最长回文子串动态规划

题目描述

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

 输入：s = "cbbd"
 输出："bb"

解题方法

1、动态规划算法

解题思路

（1）考虑回文串的性质：若一个子串是回文串并且长度大于2，则将其首尾两个字母去除后，该子串仍然是一个回文串，反过来思考，若一个子串是回文串，在其首尾分别添加一个字母，若字母相同，则形成的子串也是回文串。

（2）状态表示：回文串有三个重要的性质：起始字母下标、终止字母下标以及长度，其中长度可以由前两个性质推导得出，则使用二维数组dp(i,j)表示，dp(i,j)的值表示的也不再是区间[i,j]的最大回文子串的长度了，而是表示区间 [i,j]是否是回文串。

若 dp(i,j)=true，表示Si....Sj是一个回文串，反之则不是一个回文串。

（3）初始化：每个字符本身就是一个回文串

for (int i = 0; i < n; i++) 
 {
     dp[i][i] = true;
 }

（4）状态转移：由（1）可得，当j-i>=3时，dp(i,j)的值由两个因素决定：s[i]与s[j]的值，dp(i+1,j-1)，并且仅当以下两个条件同时成立时，dp(i,j)为true

当j-i<3时，存在两种情况：

①j-i=1，则dp(i,j)一定为true（a、b)；

②j-i=2，若此时s[i]==s[j]，则dp(i,j)为true（ab、aa）；

其中第二种情况可以归纳到一般情况的计算中，只需要添加一个条件判断即可。

因为需要使用到dp(i+1,j-1)的值，递推时从长度较小的字符串向长度较长的字符串进行转移（即先计算较小的区间，再计算较大的区间）。

（5）代码流程：当区间大小为1时（即i==j），一定是回文串，因此只需要讨论区间长度在[2,n]之间的情况。外层循环表示每次判断的区间大小L，内层循环固定右边界（即i的大小），j的值可以由L和i推导得到（j=L+i-1)，因此不需要再加一层循环。同时需要注意左边界越界问题（j>=n)，一旦越界就可以退出当前循环，右边界不存在越界问题。

在循环中，一旦s[i]!=s[j]则表示区间[i,j]不可能形成回文串，置dp(i,j)=false；若s[i]==s[j]，当L<=3时不需要判断dp(i+1,j-1)的情况，直接置dp(i,j)=true，当L>3时，需要判断dp(i+1,j-1)，当且仅当dp(i+1,j-1)=true时，置dp(i,j)= true。

代码实现

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        // 特殊情况，直接返回字符串即可
        if (n < 2) {
            return s;
        }
 
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        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++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }
 
                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    // 处理当j-i==2时的特殊情况
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
 
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文
                // 此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

复杂度分析

（1）时间复杂度

外层循环n次，内层循环n次，则时间复杂度为O(n^2)。

（2）空间复杂度

动态规划数组存储空间为nxn，则空间复杂度为O(n^2)。

2、中心扩展算法

解题思路

（1）在动态规划方法中，每一次判断s[i]==s[j]之后，我们都会再判断dp(i+1,j-1)的情况。事实上可以考虑以回文子串为扩展中心，向（i-1,j+1）方向扩展，若s[i-1]==s[j+1]则可以扩展回文子串的长度，一旦不相等则停止继续扩展回文子串。

（2）代码流程：先枚举出所有的回文中心，再尝试向左向右同时进行扩展，最后求出所有扩展回文串的最大值得到最大回文串长度。

注意：因为奇数长度的回文串和偶数长度的回文串结构不太一样，偶数长度的回文串没有中心字符，因此枚举时需要以长度为1的子串作为回文中心（扩展得到奇数长度的回文串）也需要以长度为2的子串作为回文中心（扩展得到偶数长度的回文串）。

（3）标准模板库——pair

作用：

①pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。

pair<string, string> anon;

②另一个应用是，当一个函数需要**返回2个数据**的时候，可以选择pair。

pair<int, int> expandAroundCenter(const string& s, int left, int right)
 {
     // 省略
     return {left + 1, right - 1};
 }

性质：

①pair中的两个数据可以具有不同的数据类型。

pair<int, double> p1(1, 1.2);

②两个数据可以分别用pair的两个公有函数first和second访问。

pair<int ,double> p1;
p1.first = 1; 
p1.second = 2.5;
cout<<p1.first<<' '<<p1.second<<endl;

代码实现

class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        // 返回满足要求的回文串起始索引
        return {left + 1, right - 1};
    }
 
    string longestPalindrome(string s) {
        // 使用变量start和end跟踪最大扩展回文子串
        int start = 0, end = 0;
        // 枚举所有可能的长度为1或2的回文中心
        for (int i = 0; i < s.size(); ++i) {
            // 以一个字符作为回文中心进行扩展
            auto [left1, right1] = expandAroundCenter(s, i, i);
            // 以两个字符作为回文中心进行扩展
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
            // 更新记录
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

复杂度分析

（1）时间复杂度

回文中心共有n个，每个回文中心最多向外扩展n次，则时间复杂度为O(n^2)。

（2）空间复杂度

使用了变量start、end作为跟踪变量（常数），则空间复杂度为O(n)。

3、Manacher算法

class Solution {
public:
    int expand(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }
 
    string longestPalindrome(string s) {
        int start = 0, end = -1;
        string t = "#";
        for (char c: s) {
            t += c;
            t += '#';
        }
        t += '#';
        s = t;
 
        vector<int> arm_len;
        int right = -1, j = -1;
        for (int i = 0; i < s.size(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = min(arm_len[i_sym], right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.push_back(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }
 
        string ans;
        for (int i = start; i <= end; ++i) {
            if (s[i] != '#') {
                ans += s[i];
            }
        }
        return ans;
    }
};

（1）时间复杂度：O(n)

（2）空间复杂度：O(n)

该算法时间复杂度和空间复杂度均较低，但是算法复杂，不在掌握范围内。