区间动态规划-最长回文子串

问题：给定一个字符串，求出字符串中最长回文子串。
例如：
input “babad” output”bab”

对于最长回文子串问题，动态规划方法的核心思想是：

状态定义：定义一个二维数组 dp[i][j]，其中 dp[i][j] 表示字符串中从索引 i 到 j 的子串是否为回文串。
状态转移：状态 dp[i][j] 的值依赖于 dp[i+1][j-1] 的值，即内部子串的回文性质，以及 s[i] 和 s[j]（字符串中第 i 和第 j 个字符）是否相等。简单地说，如果内部子串是回文且当前考虑的两端字符相等，则当前子串也是回文。
初始化：单个字符总是回文串，所以对于所有 i，dp[i][i] 是 true。对于长度为 2 的子串，只需检查两个字符是否相同。
结果构建：通过遍历所有可能的子串并更新最长回文子串的记录，最终得到所求的最长回文子串。

在解决这种类型的动态规划问题时，通常需要两层循环遍历所有可能的子区间，并计算每个子区间的属性。这种方法在处理字符串相关的问题，特别是涉及子串属性的问题时非常有效。

这个动态规划方法的时间复杂度是 O(N^2)，其中 N 是字符串的长度。对于每个子串，我们只需要 O(1) 的时间来判断它是否是回文串。尽管这种方法在理论上是有效的，但在实际应用中，特别是对于较长的字符串，中心扩展法或Manacher算法可能会有更好的性能。

/**************************************************************** 
 * Description: 动态规划求最长回文子串
 * Author: Alex Li
 * Date: 2023-11-20 15:52:10
 * LastEditTime: 2023-11-20 16:56:35
****************************************************************/
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

   //我们使用一个二维布尔数组 dp 来存储信息。如果 s[i...j] 是回文串，则 dp[i][j] 为 true。
    bool  dp[n][n];
    
    string longest = "";
     //外层循环遍历所有可能的子串长度 len，从长度为 1 到 n。
    for (int len = 1; len <= n; len++) {
        //内层循环遍历所有可能的起始位置 start。
        for (int start = 0; start < n; start++) {
            int end = start + len - 1;
            if (end >= n) break;
            //如果子串长度为 1（len == 1），则子串是回文因为单个字符总是回文
            //如果子串长度为 2（len == 2），则需要检查这两个字符是否相同（s[start] == s[end]）
            //对于大于2的子串 s[start...end]，如果它的首尾字符相同，并且其内部子串 s[start+1...end-1] 也是回文串，则当前子串是回文串。 
            //(len == 1 || len == 2 || dp[start + 1][end - 1]) 这式子利用了或运算的短路模式，
            //len==1为true就不运算第二项，len==2为true就不运算第三项
            dp[start][end] = (len == 1 || len == 2 || dp[start + 1][end - 1]) && s[start] == s[end];
            

            //如果找到了更长的回文子串，则更新 longest。
            if (dp[start][end] && len > longest.size()) {
                longest = s.substr(start, len);
            }
        }
    }
    return longest;
}

int main() {
    string s;
    cin>>s;
    cout << "Longest Palindromic Substring: " << longestPalindrome(s) << endl;
    return 0;
}

这个问题还可以用中心扩展算法和Manacher算法。另篇讲解！

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

区间动态规划-最长回文子串