题目链接

关键词

解析

• 尝试一：

枚举所有的子串，并逐一判断是否为回文子串，取最长的一个作为 res 返回（超时） 超时原因：题目数据为 10^3，暴力解法时间复杂度为 O(n^2)，但由于 reverse() 的复杂度为 O(n)，所以总体为 10^9 数量级，故而超时

• 动态规划：

• 定义 dp[i][j] 表示字符串 s 从 i 到 j 的子串是否是回文子串

• 因为长度为 1 的子串本身就是回文子串，即 dp[i][i] = true

• 状态方程为：
• dp[i][j] = dp[i + 1][j - 1], {s[i] == s[j]}
• dp[i][j] = true, {s[i] == s[j], j - i <= 2}
• dp[i][j] = false, {s[i] != s[j]}

• 中心扩散法

• 因为回文串的特点，一定会有一个对称中心，所以，可以枚举所有的对称中心，然后从对称中心向两边扩散，若 s[left] == s[right]，则继续扩散，否则就停止，并返回当前长度

• 回文串在长度为奇数和偶数的时候，「回文中心」的形态不一样：
• 奇数回文串的「中心」是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
• 偶数回文串的「中心」是位于中间的两个字符的「空隙」，例如：回文串 "abba" 的中心是 "bb"

代码

• 尝试一代码：

• 动态规划代码：

• 中心扩散法代码