Leo's Studio.

LeetCode 5: Longest Palindromic Substring

字数统计: 866阅读时长: 4 min
2019/12/12

题目描述

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

解题思路

  • 中心扩展算法

    计算以字符串中的每一个字符为中心,向两边扩展的最长回文串。

    以字符串 “babad” 为例,第一个字符 ‘b’,以它为中心的最长回文串就是它本身,再看第二个字符 ‘a’,以它为中心的最长回文串是 “bab”。

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public String longestPalindrome2(String s) {
    if (s.length() < 2) {
    return s;
    }
    int[] ret = new int[2];
    for (int i = 0; i < s.length(); i++) {
    loop(ret, i, s);
    }
    return s.substring(ret[0], ret[1]);
    }

    private void loop(int[] ret, int low, String s) {
    int high = low;
    // Code 1
    while (high < s.length() - 1 && s.charAt(high + 1) == s.charAt(low)) high++;
    while (high < s.length() && low >= 0 && s.charAt(low) == s.charAt(high)) {
    high++;
    low--;
    }
    if (high - low - 1 > ret[1] - ret[0]) {
    ret[0] = low + 1;
    ret[1] = high;
    }
    }

    Code 1 处是考虑偶数回文串的情况,比如 “aa” 这种也是回文串,只要是相同字符,不管有多少位都是回文串。

    空间复杂度 时间复杂度
    O(1) O($$N ^ 2$$)
  • 动态规划

    使用一个二维数组来缓存回文串的判断,dp[i][j] 表示从下标 i 到 j 的字符串是否为回文串。

    状态转移方程如下:

    1
    dp[i][j] = dp[i+1][j-1] && S(i) == S(j)

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public String longestPalindrome(String s) {

    if (s.length() < 2) {
    return s;
    }

    String max = s.substring(0, 1);
    boolean[][] dp = new boolean[s.length()][s.length()];
    for (int i = s.length() - 1; i > -1; i--) {
    for (int j = i; j < s.length(); j++) {
    // Code 1
    dp[i][j] = (s.charAt(i) == s.charAt(j))
    && (j - i < 3 || dp[i + 1][j - 1]);
    if (dp[i][j] && j - i + 1 > max.length()) {
    max = s.substring(i, j + 1);
    }
    }
    }
    return max;
    }

    Code 1 代码处中的 j - i < 3 是考虑 “a”、”aa” 和 “aba” 这些情况。

    空间复杂度 时间复杂度
    O($$N^2$$) O($$N^2$$)
  • Manacher 算法

    这里有篇详细介绍的文章,可移步:最长回文子串——Manacher 算法

    相对于前面两种解法,Manacher 算法有以下优点:

    • 通过在字符间插入特殊字符,使得字符串的长度变成奇数,不会影响最终结果,但不用考虑偶数回文串的情况
    • 复用已经计算好的结果

    代码如下:

    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
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    public String longestPalindrome(String s) {
    if (s.length() < 2) {
    return s;
    }
    StringBuilder builder = new StringBuilder();
    builder.append("#");
    for (int i = 0; i < s.length(); i++) {
    builder.append(s, i, i + 1);
    builder.append("#");
    }
    s = builder.toString();
    // 下标为 i 的字符为中点的最长回文串的半径
    int[] dp = new int[s.length()];
    builder.delete(0, builder.length());

    // 计算过的区域
    int maxRight = 0;
    int maxLen = 0;
    // maxRight 对应的回文串的中点
    int pos = 0;

    for (int i = 0; i < s.length(); i++) {

    if (i < maxRight) {
    // 2 * pos - i 表示,i 关于 pos 对称的点
    dp[i] = Math.min(dp[2 * pos - i], maxRight - i + 1);
    } else {
    // 默认值为 1
    dp[i] = 1;
    }

    while (i + dp[i] < s.length() && i - dp[i] >= 0 && s.charAt(i + dp[i]) == s.charAt(i - dp[i])) {
    // 中点扩散
    dp[i] += 1;
    }

    if (i + dp[i] - 1 > maxRight) {
    maxRight = i + dp[i] - 1;
    pos = i;
    }

    maxLen = Math.max(maxLen, dp[i]);
    if (maxLen == dp[i]) {
    if (builder.length() > 0) {
    builder.delete(0, builder.length());
    }
    builder.append(s, i - dp[i] + 1, i + dp[i]);
    }

    }

    return builder.toString().replace("#", "");

    }
    空间复杂度 时间复杂度
    O($$N$$) O($$N$$)
CATALOG
  1. 1. 题目描述
  2. 2. 解题思路