686 字
3 分钟
Leetcode->最长回文子串
题目
给你一个字符串 s
,找到 s
中最长的回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s
仅由数字和英文字母组成
解题:key:
①暴力解法
TIP记录最长回文子串的长度和起始下标,这样只需要在最后返回的时候进行截取即可,提高性能
时间复杂度: O(n^3)
空间复杂度: O(1)
/**
* @param {string} s
* @return {string}
*/
// 验证子串 s[left...right]是否是回文串
var validPalindromic = (s, left, right) => {
while (left < right) {
if (s[left] != s[right])
return false
left++
right--
}
return true
}
var longestPalindrome = function (s) {
let len = s.length
if (len < 2)
return s
// 记录最长回文子串的 长度 和 起始下标
let maxLen = 1
let begin = 0
// 枚举所有长度大于1的子串s[i...j]
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++) {
// 大于当前最长回文子串的长度 且 是回文串
if (j - i + 1 > maxLen && validPalindromic(s, i, j)) {
// 更新
maxLen = j - i + 1
begin = i
}
}
}
return s.substring(begin, begin + maxLen)
};
②动态规划
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
let len = s.length
if (len < 2) {
return s
}
let maxLen = 1
let begin = 0
// dp[i][i]表示 子串s[i...j] 是否是回文串
let dp = Array.from(new Array(len), () => new Array(len))
// 初始化长度为1的子串都是回文串
for (let i = 0; i < len; i++) {
dp[i][i] = true
}
// 先枚举子串长度 从2开始
for (let L = 2; L <= len; L++) {
// 枚举左边界
for (let i = 0; i < len; i++) {
// 计算右边界 L = j - i + 1
let j = L + i - 1
// 右边界越界 退出循环
if (j >= len) {
break
}
if (s[i] != s[j]) {
dp[i][j] = false
} else {
if (j - i < 3) {
dp[i][j] = true
} else {
dp[i][j] = dp[i + 1][j - 1]
}
}
// 表明子串s[i...j]是回文串,记录长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1
begin = i
}
}
}
return s.substring(begin, begin + maxLen)
};
③中心扩展算法
TIP枚举回文子串的中心并尝试扩展,直到无法扩展
/**
* @param {string} s
* @return {string}
*/
var expandAroundCenter = (s, left, right) => {
while (left >= 0 && right < s.length && s[left] == s[right]) {
--left
++right
}
return right - left - 1
}
var longestPalindrome = function (s) {
const len = s.length
let maxLen = 1
let begin = 0
for (let i = 0; i < len - 1; i++) {
const oddLen = expandAroundCenter(s,i,i)
const evenLen = expandAroundCenter(s,i,i+1)
const curLen = Math.max(oddLen,evenLen)
if(curLen > maxLen){
maxLen = curLen
begin = i - Math.floor((maxLen - 1) / 2);
}
}
return s.substring(begin, begin + maxLen);
};
Leetcode->最长回文子串
https://blog.oceanh.top/posts/algorithm/最长回文子串/