Loading... 看到这道题的第一印像是用dp，$dp[i][j]$ 代表 $s[i..j]$ 的回文子串最大长度，后来发现这个定义好像做不出来。 遂看答案，结果发现定义应该是代表 $s[i..j]$ 是否为回文串。 然后就是需要看如何通过现有状态得到后面的状态，首先考虑回文串如何判断，如果有 $s[i] == s[j]$，且 $j-i <= 2$ 则必为 true，如果 $dp[i+1][j-1]$ 为 true 且 $s[i] == s[j] $也肯定为 true，所以递推公式就出来了： $$ dp[i][j] = \begin{cases} \text{true}, & \text{if } s[i] = s[j] \text{ and } (j - i \le 2 \text{ or } dp[i+1][j-1] = \text{true}) \\ \text{false}, & \text{otherwise} \end{cases} $$ 然后我们考虑如何进行转移，由于$dp[i][j]$依赖$dp[i+1][j-1]$，所以我们需要从上到下，从左到右的遍历才能满足这个条件。 于是得到下面的代码： ```go func longestPalindrome(s string) string { n := len(s) start, maxLen := 0, 1 // dp[i][j] 代表s[i..j]是否为回文串 dp := make([][]bool, n) for i := 0; i < n; i++ { dp[i] = make([]bool, n) } for j := 1; j < n; j++ { for i := 0; i < j; i++ { // 如果 s[i] == s[j] 且j-i<=2肯定是回文，或者i+1..j-1是回文也肯定是回文 // 因为依赖i+1,j-1所以需要i先更新，j后更新才能保障依赖项 if s[i] == s[j] && (j - i <= 2 || dp[i+1][j-1]) { dp[i][j] = true if j - i + 1 > maxLen { maxLen = j - i + 1 start = i } } } } return s[start:start+maxLen] } ``` 这种方法虽然能做出来，但是明显太耗费内存，有 $O(N^2)$的空间复杂度，于是可以思考从每个字符向外扩散构造出来的回文串最大长度。 ```go func longestPalindrome(s string) string { n := len(s) start, maxLen := 0, 1 for i := 0; i < n - 1; i++ { // 奇数回文 l1, r1 := expand(s, i, i, n) // 偶数回文 l2, r2 := expand(s, i, i+1, n) if r1 - l1 + 1 > maxLen { start = l1 maxLen = r1 - l1 + 1 } if r2 - l2 + 1 > maxLen { start = l2 maxLen = r2 - l2 + 1 } } return s[start:start+maxLen] } func expand(s string, left, right, n int) (int, int) { for left >= 0 && right < n && s[left] == s[right] { left-- right++ } return left+1, right-1 } ``` 最后再拓展一个经典算法，马拉车（Manacher），利用了回文串的对称性质，记录了之前计算出来的回文串状态用来减少计算量，从而将时间复杂度降至 $O(n)$。 首先是需要保证字符串长度为奇数，所以在每个字符之间插入一个 `#`，首尾分别加上一个 `^` 和 `$`，作为 `t` 定义一个 `p[i]`，为位置 `i` 的回文串最大半径长度，`center` 为回文串中心点，`right` 为回文串边界。 遍历 `[1, n-2]` 的每个点： - 当 i < right 时，计算 i 相对于 center 的对称点 mirror，mirror = center * 2 - i，p[i] = min(right-i, p[mirror])。因为对称性质我们可以取 p[mirror]，但是如果这个长度超出了 i 到 right 的边界长度，这里就是没有计算过的地方了，所以不能直接复用，只能取 right - i，于是有了上面的公式。 - 向外拓展计算回文串 for t[i + (1 + p[i])] == t[i - (1 + p[i])]; p[i]++。 - 如果 i + p[i] > right，说明找到了下一个回文串，需要更新回文串边界和中心点，center = i，right = i + p[i]。 - 如果 p[i] > maxLen，说明找到了更长的回文串，需要更新 maxLen = p[i]，centerIndex = i。 最终，我们得到的 centerIndex 和 maxLen 即是答案，当然因为字符串拓宽了一倍的长度，所以需要还原原本的 start，start = (centerIndex - maxLen) / 2，值得注意的是，这里的 maxLen 是拓展字符串的回文串半径，也是原字符串的回文串长度。 所以最终答案即 `s[start:start+maxLen]` ```go func longestPalindrome(s string) string { t := "^#" + strings.Join(strings.Split(s, ""), "#") + "#$" n := len(t) center, right := 0, 0 // p[i]代表回文串中心到某一边的半径 // 因为是拓展了一倍长度的#，所以这个半径就是实际的回文串长度 p := make([]int, n) centerIndex, maxLen := 0, 1 for i := 1; i < n-1; i++ { // 回文对称利用，如果超出回文边界则取right-i，否则取对称点的长度 mirror := 2 * center - i if i < right { p[i] = min(p[mirror], right - i) } // 向外扩展搜索回文串 for t[i + (1 + p[i])] == t[i - (1 + p[i])] { p[i]++ } if i + p[i] > right { center = i right = i + p[i] } if p[i] > maxLen { maxLen = p[i] centerIndex = i } } // ^#a#b#a#$ 的最长中心点是4，maxLen是3，所以这里获取原始的起点就是如下公式 start := (centerIndex - maxLen) / 2 return s[start:start+maxLen] } ``` Last modification：July 13, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
