描述

题目描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

示例
输入："abc1234321ab",12
返回值：7

知识点：字符串
难度：⭐⭐⭐

题解

方法一：中心扩散

解题思路：

image-20210718145536852

算法流程：
  • 每个字符都可以尝试作为中心点看，会出现两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况
  • 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可
    • 从left到right开始向两边扩散、比较，如果相等则继续扩散比较
    • 如果不相等则剪枝，不用再继续扩散比较
  • 计算每次比较的回文子串长度，取最大
Java 版本代码如下：
import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        if(n < 2) {
            return n;
        }
        // 最大长度
        int res = 0; 
        // 每个字符都可以尝试作为中心点
        for(int i = 0; i < n; i++) {
            // 两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况
            // 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可
            int len = helper(A, i, i) > helper(A, i, i+1) ? helper(A, i, i) : helper(A, i, i + 1);
            // 更新最大长度
            res = Math.max(res, len);
        }
        return res;
    }

    public int helper(String A, int left, int right) {
        // 从left到right开始向两边扩散、比较
        while(left >= 0 && right < A.length()) {
            // 如果相等则继续扩散比较
            if(A.charAt(left) == A.charAt(right)) {
                left--;
                right++;
                continue;
            }
            // 如果不相等则剪枝，不用再继续扩散比较
            break;
        }
        // "+1"是因为通过下标计算子串长度
        // "-2"是因为上边的while循环是当索引为left和right不想等才退出循环的
        // 因此此时的left和right是不满足的，需要舍弃
        return right - left + 1 - 2;

    }
}
复杂度分析：

时间复杂度 O(N^2)：平均需要遍历每个结点作为中心点，还需要从中心点向左右扩散比较
空间复杂度 O(1)：只用到常量

方法二：动态规划

解题思路：

维护一个布尔型的二维数组dp，dp[i][j]表示 i 到 j 的子串是否是回文子串

每次先判断边界字符是否相等，再取决于上个状态的判断结果

算法流程：
  • 维护一个布尔型的二维数组dp，dp[i][j]表示 i 到 j 的子串是否是回文子串
  • 从长度0到字符串长度n进行判断
  • 选定起始下标 i 和终止下标 j， i 和 j 分别为要比较的字符串的左右边界指针
  • 从左右边界字符开始判断，即 A.charAt(i) == A.charAt(j)
    • 当相等时，还要判断当前长度 c 是否大于1，不大于则表明只有两个字符的字符串，一个或两个字符肯定是回文串，如“11”
    • 判断的长度大于1时，因为最左右的字符已经相等，因此取决于上一次的子串是否是回文子串, 如 “12121”
  • 更新回文串的最大长度
Java 版本代码如下：
import java.util.*;
public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // 动态规划：i到j的子串是否是回文子串
        boolean[][] dp = new boolean[n][n];
        int max = 0;
        // 字符串长度差 c = j-i，即当前要比较的字符串长度，这里可以 c <= n / 2 + 1，减少判断次数
        for(int c = 0; c <= n + 1; c++) {
            // 起始下标，范围取决于要判断的字符串长度c
            // i 和 j 分别为要比较的字符串的左右边界指针
            for(int i = 0; i < n - c; i++) {
                // 终点下标
                int j = c + i;
                // 左右边界的字符相等
                if(A.charAt(i) == A.charAt(j)) {
                    // c <= 1表示只有两个字符的字符串，一个或两个字符肯定是回文串
                    if(c <= 1) {
                        dp[i][j] = true;
                    } else {
                        // 对于两个字符以上的字符串
                        // 因为最左右的字符已经相等，因此取决于内层的子串是否是回文子串
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    // 更新回文串的最大长度，c代表判断的子串长度，越来越大
                    if(dp[i][j]) {
                        max = c + 1;
                    }
                }
            }
        }
        return max;
    }
}
复杂度分析：

时间复杂度 O(N^2)：N为字符串长度，平均判断的子串长度从0到N
空间复杂度 O(N^2)：需要维护二维数组，代表转移方程的状态