LeetCode5-最长回文子串

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/longest-palindromic-substring/

中文链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

题目详述

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

示例 1：

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

示例 2：

1
2
输入: "cbbd"
输出: "bb"

题目详解

  • 由于字符串长度小于1000，因此我们可以用 O(n^2)O(n2) 的算法枚举所有可能的情况。
  • 首先枚举回文串的中心 i，然后分奇数长度和偶数长度两种情况向两边扩展边界，直到遇到不同字符为止。
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
public class LeetCode_00005 {

    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return "";
        }
        char[] cs = s.toCharArray();
        int first = 0, last = -1;
        for (int i = 0; i < cs.length; ++i) {
            int[] border = getBorder(cs, i, i);     // 从 cs[i] 向外扩展
            if (border[1] - border[0] > last - first) {
                first = border[0];
                last = border[1];
            }
            border = getBorder(cs, i, i + 1);       // 从 cs[i]、cs[i + 1] 向外扩展
            if (border[1] - border[0] > last - first) {
                first = border[0];
                last = border[1];
            }
        }
        return String.valueOf(cs, first, last - first + 1);
    }

    private int[] getBorder(char[] cs, int l, int r) {
        while (l >= 0 && r < cs.length && cs[l] == cs[r]) {
            --l;
            ++r;
        }
        return new int[]{l + 1, r - 1};
    }
}
  • 求最长回文子串的经典方法是用 manacher 算法。
  • 时间复杂度为 O(n)。
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
public class LeetCode_00005 {

    public String longestPalindrome(String s) {
        StringBuilder sb = new StringBuilder("^");
        for (char c : s.toCharArray()) {
            sb.append('#').append(c);
        }
        sb.append("#$");
        char[] cs = sb.toString().toCharArray();
        int[] p = new int[cs.length];
        int center = 0;
        int right = 0;
        int resc = 0;
        for (int i = 1; cs[i] != '$'; ++i) {
            p[i] = right > i ? Math.min(p[(center << 1) - i], right - i) : 1;
            while (cs[i + p[i]] == cs[i - p[i]]) {
                ++p[i];
            }
            if (i + p[i] > right) {
                right = i + p[i];
                center = i;
            }
            if (p[i] > p[resc]) {
                resc = i;
            }
        }
        sb = new StringBuilder();
        int cnt = p[resc] - 1;
        for (int i = resc - p[resc] + 2; cnt-- != 0; i += 2) {
            sb.append(cs[i]);
        }
        return sb.toString();
    }
}