LeetCode-最长回文子串（005）

🕗 发布于 2024-12-29 21:12 leetcode 算法职场和发展

一.题目描述

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

二.示例

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

三.提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

四.解法:

方法一：动态规划

我们定义 f[i][j] 表示字符串 s[i..j] 是否为回文串，初始时 f[i][j]=true。

接下来，我们定义变量 k 和 mx，其中 k 表示最长回文串的起始位置，$mx$ 表示最长回文串的长度。初始时 k=0, mx=1。

考虑 f[i][j]，如果 s[i]=s[j]，那么 f[i][j]=f[i+1][j−1]；否则 f[i][j]=false。如果 f[i][j]=true 并且 mx<j−i+1，那么我们更新 k=i, mx=j−i+1。

由于 f[i][j] 依赖于 f[i+1][j−1]，因此我们需要保证 i+1 在 j−1 之前，因此我们需要从大到小地枚举 i，从小到大地枚举 j。

时间复杂度 O(n2)，空间复杂度 O(n2)。其中 n 是字符串 s 的长度。

五.代码

Java代码

class Solution {
    public String longestPalindrome(String s) {
        // 获取字符串的长度
        int n = s.length();
        // 创建一个二维布尔数组，用于记录子串是否为回文
        boolean[][] f = new boolean[n][n];
        
        // 初始化所有单个字符的子串为回文
        for (var g : f) {
            Arrays.fill(g, true);
        }
        
        // 初始化最长回文子串的起始索引和长度
        int k = 0, mx = 1;
        
        // 从字符串的倒数第二个字符开始，向前遍历
        for (int i = n - 2; i >= 0; --i) {
            // 从当前字符的下一个字符开始，向后遍历
            for (int j = i + 1; j < n; ++j) {
                // 初始化 f[i][j] 为 false，表示子串 s[i...j] 不是回文
                f[i][j] = false;
                
                // 如果 s[i] 和 s[j] 相等，检查子串 s[i+1...j-1] 是否为回文
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1];
                    
                    // 如果子串 s[i...j] 是回文，并且长度大于当前最大长度，更新最大长度和起始索引
                    if (f[i][j] && mx < j - i + 1) {
                        mx = j - i + 1;
                        k = i;
                    }
                }
            }
        }
        
        // 返回最长回文子串
        return s.substring(k, k + mx);
    }
}

注释说明
    ·二维布尔数组 f：用于记录子串 s[i...j] 是否为回文，初始时所有单个字符的子串都被认为是回文。
    ·双重循环：外层循环从字符串的倒数第二个字符开始，内层循环从当前字符的下一个字符开始，逐步检查每个子串。
    ·回文检查：如果 s[i] 和 s[j] 相等，则检查 s[i+1...j-1] 是否为回文。
    ·更新最长回文子串：如果找到更长的回文子串，更新其起始索引 k 和长度 mx。
    ·返回结果：使用 substring 方法返回最长回文子串。

方法二：枚举回文中间点

我们可以枚举回文中间点，向两边扩散，找到最长的回文串。

时间复杂度 O(n2)，空间复杂度 O(1)。其中 n 是字符串 s 的长度。