最长回文子串(动规 + 中心拓展)

BM73 最长回文子串

1. 动态规划

能够将所有的子串是否是回文的信息,保存在dp表里面.
时间/空间复杂度都是: O(n*n)

(1)状态表示:

首先我们这样想,如何表示出所有的子串?
我们假设 i 为子串的起始位置, j 为子串的结束位置,那我们就可以暴力枚举出所有的子串.当枚举完一个子串后, j 就不用从头开始了, 因为这时的子串和之前是一样的, 枚举下一个子串时 j 直接从 i 的位置开始即可.

暴力枚举的过程用两层for循环即可完成, 即用一个二维的dp表. 在二维dp表中,用横坐标表示起始位置 i ,用纵坐标表示结束位置 j .

如下图分析可知, 我们只需要使用dp表的上三角(i<=j) 部分即可:

在dp表中填上 true 或 false 即可知道该子串是否是回文了.

dp[i][j]表示: s 字符串 [i, j] 区间的子串是否是回文串.

(2)状态转移方程

要是回文串,首尾字符必须相同吧, 所以根据 s[i] 和 s[j] 的关系进行推导:
(1) s[i] != s[j], dp[i][j] = false
(2) s[i] == s[j] 时又有三种情况:
a. i==j 只有一个字符,是回文, dp[i][j] = true
b. i+1 = j 是相邻的, 也是回文, dp[i][j] = true
c. i 和 j 之间有别的字符了,则要去 [i+1, j-1] 的区间找了,即 dp[i+1][j-1], 如果它是 true, 则 dp[i][j] 是true, 否则 dp[i][j] 是 false.

(3)初始化

对 dp表 进行初始化时为了在后续填表时避免越界, 此时有可能会越界的是 dp[i+1][j-1].
当 i 和 j 相等或是 i 和 j 相邻的时候, 再进行 i + 1 和 j - 1 后, j > i 了, 但是我们在前面已经分析过了,使用的是dp表的上三角(i<=j), 此时不符合条件了. 但是其实这里是不会越界的, 因为会越界的两种情况就是上述分析的 a,b 两种情况, 已经特判过了.
所以, 可以不用进行初始化.

(4)填表顺序

我们填 (i, j) 位置时要用到 (i+1, j-1) 位置, 所以填表顺序整体是从下往上填写每一行.

(5)返回值

在 dp表 中是 true 的位置就是回文串, 知道了回文串的起始位置和结束位置, 一定可以计算出最长回文串的长度.

代码实现如下:

class Solution 
{
public:int getLongestPalindrome(string A) {//动态规划(n*n / n*n)//能够将所有的子串是否是回文的信息,保存在dp表里//dp[i][j]表示: s 字符串 [i,  j] 的子串是否是回文串.int n = A.size();vector<vector<bool>> dp(n, vector<bool>(n));int ret = 0;for(int i = n-1; i >= 0; i--){for(int j = i; j < n; j++) //注意: j >= i {//第一种情况: A[i] != A[j], 初始化默认是false//把后面三种情况合并在一起if(A[i] == A[j])dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true;if(dp[i][j])ret = max(ret, j - i + 1);}}return ret;}
};

2. 中心拓展算法

中心拓展就是使用两个变量表示子串的起始位置和结束位置, 同时进行向左向右扩展, 这个过程可以分为奇数次扩展和偶数次扩展, 在计算出两种扩展的最大值即可.
时间复杂度: O(n)
空间复杂度: O(1)

代码实现如下:

class Solution 
{
public:int getLongestPalindrome(string A) {int n = A.size();int len = 1;//中心拓展算法(n*n / 1)//从下标为1的地方开始遍历for(int i = 1; i < n; i++){// 奇数次扩int left = i - 1, right = i + 1;while(left >= 0 && right < n && A[left] == A[right]){left --;right++;}len = max(len, right - left - 1);// 偶数次扩left = i - 1, right = i;while(left >= 0 && right < n && A[left] == A[right]){left --;right++;}len = max(len, right - left - 1);}return len;
};