# 5 最长回文子串
# 题目链接
# 难度：中等
# 思路:
中心扩展法
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 想
# 一
# 想
# 再
# 看
# 答
# 案
# 代码：
双指针：中心扩展
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let result = s[0] || ''
// 遍历整个字符串
for (let i = 0; i < s.length; i++) {
// 选择一个中心点 j<=2尝试偶数和奇数两种形式的中心点
for (let j = 1; j <= 2; j++) {
// 对称回文或者中心点回文
let left = i, // 左
right = i + j // 右
// 当左右两遍的字符相同时 向外扩展直到两端不相同
// 左右的边界
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--, right++ // 扩展
}
// 找到回文
let length = right - left - 1 // (right - 1) - (left + 1) + 1
// 对比 更新回文
if (length > result.length) {
result = s.substr(left + 1, length)
}
}
}
return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
动态规划: 中心扩展
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let n = s.length
let res = ''
let dp = Array.from(new Array(n), () => new Array(n).fill(0))
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])
if (dp[i][j] && j - i + 1 > res.length) {
res = s.substring(i, j + 1)
}
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 鼓励我一下：
觉得还不错的话，给我的项目点个star吧