5_Longest_Palindromic_Substring

题目描述

image.png

思路：动态规划

一、观察
成为回文串有什么条件？从最简单的字符串来看，即1个字符的情况，"b"，一定是个回文串。
在这个基础上再添加一个字符使之成为回文串呢，只能添加b，"bb"。
三个字符的情况呢？假设前两个字符为"ba"，发现第三个字符只能填"b"。
规律就是，回文串去掉首位两个字符后，剩下的子串仍然为回文串，感觉回文串的定义就是递归的哎。
不由得想到动态规划。

二、回文串的判断：状态转移方程
既然是找最大回文子串，那就是先判断这个子串是不是回文串，再求最大长度呗。
dp[i][j]代表子串区间[i,j]是否为回文串，是1 否0。 i<=j。
当 i = j 时，只有一个字符，肯定是回文串；如果 i = j + 1，说明是相邻字符，此时需要判断 s[i] 是否等于 s[j]；如果i和j不相邻，即 i - j >= 2 时，除了判断 s[i] 和 s[j] 相等之外，dp[i + 1][j - 1] 若为真，就是回文串，通过以上分析，可以写出递推式如下：
令f(i,j) = dp[i][j]

image.png

即，想知道区间[i,j]是否为回文串，需先知道区间[i+1, j-1]是否为回文串。弄个二维数组dp[n][n]开始打表吧，因为i<=j所以打表只需打一半。打表过程要注意，求解dp[i][j]时，要保证dp[i+1][j-1]已经被计算过了，否则无法转移状态。
举个例子，s="babad"，当求解dp[0][4]时，dp[1][3]必须已经被计算过了。即j=4的时候，要保证j=3的所有子串都遍历过了。因此外层遍历j，内层遍历i。

for (j = 0 ~ 4)
    for (i = 0 ~ j)

手动模拟一下这个过程：
j = 0: f(0,0) = 0
j = 1: f(0,1) = 0
         f(1,1) = 1
j = 2: f(0,2) = f(1,1) && (s[0] == s[2]) = 1&1 = 1
         f(1,2) = 0
         f(2,2) = 1
j = 3: f(0,3) = f(1,2) && (s[0] == s[3]) = 0
         f(1,3) = f(2,2) && (s[1] == s[3]) = 1
         f(2,3) = 0
         f(3,3) = 1
...

三、最长
打表过程中需计算每个回文子串(条件：dp[i][j] == 1)的长度，
并维护当前的最大长度len，以及此时子串的起始位置left，以便获得子串内容 s.substr(left, len)。

代码

#include <iostream>
#include <string>
using namespace std;

string longestPalindrome(string s) {
    if (s.empty()) return "";
    int n = s.size();
    int dp[1000][1000] = {0};
    int len = 1, left = 0;
    for (int j = 0; j < n; j++) {
        for (int i = 0; i <= j; i++) {
            dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i + 1][j - 1]);
            if (dp[i][j] == 1 && j - i + 1 > len) {
                len = j - i + 1;
                left = i;
            }
        }
    }
    return s.substr(left, len);
}


int main() {
    string s = "babad";
    cout << longestPalindrome(s) << endl;
}

总结与TODO

还有一种马拉车算法，以后研究一下
https://blog.csdn.net/u013309870/article/details/70742315
https://segmentfault.com/a/1190000003914228
https://www.cnblogs.com/grandyang/p/4464476.html