力扣 (opens new window)

题目

给你一个字符串 s，找到 s 中最长的回文子串。

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

题解

动态规划

假设起始坐标是i,j，p(i,j)的布尔值表示字符串从第i个字符到第j个字符是否是回文串，$S_i$ 表示第i个字符

状态转移方程：

$$P(i,j)=P(i+1,j-1)\wedge {(S}_{i}=={S}_{j})$$

再考虑边界条件：

1. 对于长度为1的子串，都是回文串，即$P(i,i)=true$

2. 对于长度为2的子串，只要两个字符相同，就是回文串，即$P(i,i+1)=(S_i==S_{i+1})$

代码：

public String longestPalindrome(String s) {
    if (s.length()<2){
        return s;
    }
    int maxLen = 0 ,begin = 0;
    boolean[][]dp = new boolean[s.length()][s.length()];
    //从回文串长度为1开始遍历
    for (int len = 1; len <=s.length() ; len++) {
        for (int i = 0; i < s.length(); i++) {
            int j = i+ len -1;
            if (j>=s.length()){
                break;
            }
            if (s.charAt(i) != s.charAt(j)){
                dp[i][j] = false;
            }else {
                //长度为1和2的子串，直接判断
                if (len <= 2){
                    dp[i][j] = true;
                }else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            if (dp[i][j] && j-i+1>maxLen){
                begin = i;
                maxLen = j-i+1;
            }
        }
    }
    return s.substring(begin,begin+maxLen);
}

复杂的分析

时间复杂度：$O(n^2)$，需要经历两层循环。

空间复杂度：$O(n^2)$，需要建立一个二维数组。

中心扩散法

回文串一定是对称的，所以我们可以每次循环选择一个中心，然后从中心向两边扩散，判断左右字符是否相等。

代码：

public String longestPalindrome(String s) {
    if (s.length()<=1){
        return s;
    }
    int maxLen = 0,begin = 0;
    for (int i = 0; i < s.length(); i++) {
        int l1 = expandAroundCenter(s,i,i);
        int l2 = expandAroundCenter(s,i,i+1);
        if (l2>l1){
            l1 = l2;
        }
        if (l1>maxLen){
            begin = i-(l1-1)/2;
            maxLen = l1;
        }
    }
    return s.substring(begin,begin+maxLen);
}

复杂度分析

时间复杂度：$O(n^2)$，需要经历两层循环。

空间复杂度：$O(1)$，只需要常数的空间。

Manacher算法

Manacher算法是一种用来寻找最长回文子串的线性方法，由一个叫做Manacher的人在1975年发明的，这个算法在中心扩散的基础上进行改进，利用了回文串的对称性，减少了重复的判断。

具体的算法思想是：

1. 当计算出$S_i$的回文半径时，如果$S_i$的回文半径为$R_i$

2. 在以[${s}_{i+1}$,${s}_{i+{R}_{i}}$]这段字符为中心点进行扩散时，根据回文对称性，可以在$s_i$的左侧找到中心点的对应点。而这个对应点的回文半径是计算过的，则可以推出要求的中心点的最小半径，再此基础上继续扩散。

3. 具体来说，就是当计算位于$s_i$右侧且在其对称半径内的点$s_j$，找到左侧对称点${S}_{2\times i-j}$,从之前的计算得到该对称点的回文半径${R}_{2\times i-j}$，则有：

   $${R}_{j} >= min({R}_{2\times i-j}, {R}_{i}+i-j)$$

4. 计算出$s_j$的最小半径后，在这个基础上继续扩散，直到无法扩散为止。

5. 为了避免讨论奇偶性，我们在字符串的每个字符之间插入一个特殊字符，比如#，这样就可以把奇偶性统一起来了。

代码：

public String longestPalindrome(String s) {
    if (s.length() <= 1) {
        return s;
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        sb.append('#').append(s.charAt(i));
    }
    sb.append('#');
    int[] lens = new int[sb.length()];
    int begin = 0, end = 0, right = -1, len = 0, c = 0, leftI = 0;
    for (int i = 0; i < sb.length(); i++) {
        //如果当前字符在右边界内，可以利用之前计算的结果
        if (right >= i) {
            leftI = 2 * c - i;
            len = Math.min(lens[leftI], right - i);
            //在求出的最小半径的基础上继续扩散
            len = expand(sb, i - len, i + len);
        } else {
            len = expand(sb, i, i);
        }
        lens[i] = len;
        //当前字符的对称半径超过了之前得到的有边界，更新中心点和右边界
        if (i + len > right) {
            c = i;
            right = i + len;
        }
        //更新最大回文子串的起始位置
        if (len * 2 > end - begin) {
            end = i + len;
            begin = i - len;
        }
    }
    StringBuilder result = new StringBuilder();
    for (int i = begin; i <= end; i++) {
        if (sb.charAt(i) != '#') {
            result.append(sb.charAt(i));
        }
    }
    return result.toString();
}

public int expand(StringBuilder s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return (r - l - 2) / 2;
}

复杂度分析

时间复杂度：$O(n)$，虽然有两层循环，但是第二层循环在进行扩展时，要么是在有边界的基础上扩展，然后更新右边界，要么只会进行一步。所以总的时间复杂度是$O(n)$。

空间复杂度：$O(n)$，需要建立一个数组。