topic5

最长回文子串

1. 题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

2. 示例

示例1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2：

输入：s = "cbbd"
输出："bb"

示例3：

输入：s = "a"
输出："a"

示例4：

输入：s = "ac"
输出："a"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母（大写和/或小写）组成

3. 解题

动态规划法： 设dp[i] 为以下标为i的元素为结尾的字符串中回文串的最大长度，则有 dp[0] = 1 dp[i] = max{dp[i-1], 以dp[i]为结尾元素的回文串长度} 由于循环的每一步还要求以dp[i]为结尾元素的回文串长度，因此其时间复杂度为O(n*n)(好像比这个还要大), 空间复杂度为O(n)

优化：dp数组中只有最后一位有用，因此完全可以只用一个变量存储最大回文串长度dp[i]，同时用另一个变量存储dp[i-1].此时时间复杂度不变，空间复杂度降为：O(1)

中心扩展法

• 从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。举个例子，str = acdbbdaa 我们需要寻找从第一个 b（位置为 33）出发最长回文串为多少。怎么寻找？ 首先往左寻找与当期位置相同的字符，直到遇到不相等为止。 然后往右寻找与当期位置相同的字符，直到遇到不相等为止。 最后左右双向扩散，直到左和右不相等。 时间复杂度为O(n*n), 空间复杂度为O(1) 这个方法相比与动态规划来说更为直观，且性能更好。