当前位置：首页 > news >正文

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

news 来源：原创 2025/8/23 3:11:51

[BM73 最长回文子串](https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=/exam/oj?questionJobId=10&subTabName=online_coding_page)
- 1. 动态规划
- - (1)状态表示:
  - (2)状态转移方程
  - (3)初始化
  - (4)填表顺序
  - (5)返回值
- 2. 中心拓展算法

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)
在这里插入图片描述