最长回文子串

发表于 | 阅读次数: |

题目：给定一个字符串 s ，找到 s 中最长的回文子串。可以假设 s 的最大长度为 1000。

示例：

1
2
3
输入："babad"
输出："bab"
注意："aba"也是一个有效答案
1
2
输入："cbbd"
输出："bb"

方法一：最长公共子串

将 s 进行反转成 s′，找到 s 和 s′ 之间的公共子串，那么它就是最长的回文子串；此方法在没有特殊情况的时候能够正确的找出回文子串，但是当遇到 s 中除开回文子串的其它部分中存在非回文子串的反向副本时，最长公共子串法就会失败。

1
2
s = "abacdfgdcaba"
s′ = "abacdgfdcaba"

这里的 s 和 s′之间的最长公共子串为 “abacd”，显然，这不是回文。
为了解决这个问题：每当我们找到最长的公共子串的候选项时，都需要检查子串的索引是否与反向子串的原始索引相同；如果相同，继续查找是否有比目前更长的回文子串，如果不同，则跳过该项继续寻找下一个。

CODE

1
function longestPalindrome(strData) {}

方法二：中心扩展法

回文是在回文中心两侧互为镜像，因此，可以从它的中心展开，并且2n-1个中心。

CODE

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
/**
 * @param s string
 * @return val
 */
function longestPalindrome(s) {
  if (s == null || s.length() < 1) return "";
  let start = 0, end = 0;
  for (let i = 0; i < s.length(); i++) {
    const len1 = expandAroundCenter(s, i, i);
    const len2 = expandAroundCenter(s, i, i + 1);
    const len = Math.max(len1, len2);
    if (len > end - start) {
      start = i - (len - 1) / 2;
      end = i + len / 2;
    }
  }

  return s.substring(start, end + 1);
}

/**
 * @param s string
 * @param left int
 * @param right int
 * @return val
 */
function expandAroundCenter(s, left, right) {
  let L = left, R = right;
  while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
    L--;
    R++;
  }

  return R - L - 1;
}