LeetCode 最长回文子串问题解析

主题：LeetCode 最长回文子串问题解析

一、问题背景

在 LeetCode 上，"最长回文子串"问题要求我们在给定的字符串中寻找最长的回文子串。回文子串是指正着读和反着读都一样的子串。例如，对于字符串"babad"，最长的回文子串可以是"bab"或"aba"。

二、问题分析

该问题可以通过多种方法解决，包括暴力破解法、动态规划法、中心扩散法等。下面我们将详细介绍动态规划法的解题思路。

三、动态规划法解题思路

动态规划法的核心思想是，如果一个字符串的头尾两个字符相同，并且去掉这两边后的子串仍然是回文串，则该字符串也是回文串。基于这一特性，我们可以构建一个动态规划表，以减少重复的计算。

1. 初始化：创建一个二维数组dp，其中dp[i][j]表示字符串从索引i到索引j的子串是否是回文串。初始化时，因为单个字符本身就是回文串，所以设置dp[i][i]为true。

2. 遍历：对于长度大于1的子串，如果它两边的字符相等，并且去掉这两边后的子串仍然是回文串（即dp[i+1][j-1]为true），则这个子串也是回文串。

3. 更新最长回文子串：在遍历过程中，同时记录下最长回文子串的起始和结束位置。

4. 返回结果：遍历完成后，返回最长回文子串。

四、代码实现

public String longestPalindrome(String s) {
    int n = s.length();
    if (n < 2) {
        return s;
    }
    boolean[][] dp = new boolean[n][n];
    int maxLen = 1;
    int start = 0;
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    for (int j = 1; j < n; j++) {
        for (int i = 0; i < j; i++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j - i <= 2) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                start = i;
            }
        }
    }
    return s.substring(start, start + maxLen);
}

五、算法复杂度分析

• 时间复杂度：O(n^2)，因为需要对dp数组进行全面的填写，其中n是字符串的长度。
• 空间复杂度：O(n^2)，因为需要存储一个n*n的二维数组dp。

六、总结

动态规划法是解决最长回文子串问题的有效方法之一。通过构建动态规划表，我们可以减少重复的计算，从而提高算法的效率。在实际应用中，可以根据具体问题场景选择合适的解题方法。