LeetCode-5. Longest Palindromic Substring

发表于 分类于

问题描述

Given a string s, return the longest palindromic substring in s.

Example 1:

1
2
3
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

1
2
Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

解答

中心扩散法

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
29
30
31
32
33
34
35
36
/*
 * @Description: 5. Longest Palindromic Substring
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = function (s) {
  if (!s || !s.length) {
    return ''
  }

  let start = 0
  let end = 0

  const expandAroundCenter = (s, left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--
      right++
    }
    return right - left - 1
  }

  for (let i = 0; i < s.length; i++) {
    let len1 = expandAroundCenter(s, i, i)
    let len2 = expandAroundCenter(s, i, i + 1)
    let len = Math.max(len1, len2)
    if (len > end - start + 1) {
      start = i - Math.floor((len - 1) / 2) // len可能是偶数或者奇数，计算左边界时，len需要减一
      end = i + Math.floor(len / 2)
    }
  }
  return s.substring(start, end + 1)
}

写法二

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
29
30
31
32
33
34
35
36
37
38
39
40
/*
 * @Description: 5. Longest Palindromic Substring
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = function (s) {
  if (!s || !s.length) {
    return ''
  }

  let start = 0
  let end = 0

  const expandAroundCenter = (s, left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--
      right++
    }
    return [left + 1, right - 1]
  }

  for (let i = 0; i < s.length; i++) {
    let pos1 = expandAroundCenter(s, i, i)
    let pos2 = expandAroundCenter(s, i, i + 1)
    let len1 = pos1[1] - pos1[0] + 1
    let len2 = pos2[1] - pos2[0] + 1
    if (len1 > len2 && len1 > end - start + 1) {
      start = pos1[0]
      end = pos1[1]
    } else if (len1 < len2 && len2 > end - start + 1) {
      start = pos2[0]
      end = pos2[1]
    }
  }
  return s.substring(start, end + 1)
}