LeetCode 005:最长回文子串
题目地址
题目描述
plaintext
1 | 给你一个字符串 s,找到 s 中最长的回文子串。 |
解法一 中心扩散法
由简入繁
先看一个最简单的字符串,比如’aabaaabaa’;
- 第一步,i=0,这时候 res=’a’,如果回文子串长度是奇数,左边无值,右边有值,这时候最长回文子串是’a’,如果回文子串长度是偶数,res=’aa’这时候最长回文子串是’aa’;
- 第二步,i=1,这时候 res=’a’,如果回文子串长度是奇数,左边有一个值’a’,右边的值为’b’,这时候当前 i 位置最长回文子串是’a’,如果回文子串长度是偶数,res=’aa’或者 res=’ab’这时候最长回文子串是’aa’;
- 第三步,i=2,这时候 res=’b’,如果回文子串长度是奇数,左边第一个值’a’,右边第一个值为’a’,res=’aba’,左边第二个值’a’,右边第二个值’a’,res=’aabaa’,这时候最长回文子串还是’aabaa’,如果回文子串长度是偶数,最长的长度为 1;
- 第四步,i=3,…这时候最长回文子串还是第三步的’aabaa’;
- 第五步,i=4,这时候 res=’a’ … 这时候最长回文子串还是第三步的’aabaaabaa’;
….
思路
- 如果 s 的长度是 1 或者 0 的时候,s 的最长回文子串就是它本身,例如’a’,直接返回 s。
javascript
1 | if (s.length < 2) { |
- 遍历整个 s
例:s 字符串 ‘acaca’,遍历字符串,区分 i 为奇数和偶数的情况;
在 s 的范围内(所以需要m>=0 ,n<s.length
),从中心往两边去遍历,如果s[m] == s[n]
,如果如果此时回文字符串的长度大于之前最大长度则取 n-m-1
- 遍历整个 s
javascript
1 | const longestPalindrome = function (s) { |
解法二 动态规划
思路
- 状态定义
dp[i,j]:字符串 s 从索引 i 到 j 的子串是否是回文串
- true: s[i,j] 是回文串
- false:s[i,j] 不是回文串
- 转移方程
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
- s[i] == s[j]:说明当前中心可以继续扩张,进而有可能扩大回文串的长度
- dp[i+1][j-1]:true
- 说明 s[i,j]的**子串 s[i+1][j-1]**也是回文串
- 说明,i 是从最大值开始遍历的,j 是从最小值开始遍历的
- 特殊情况
- j===i:s[i]和是[j]值是同一个值
- j - i === 1:表示 s[i]和是[j]为相邻值,则需要是 s[i]===s[j]
代码
javascript
1 | const longestPalindrome = function (s) { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 易函123!
评论