【多维动态规划】Leetcode 5. 最长回文子串【中等】

最长回文子串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

解题思路

动态规划的思路是利用一个二维数组 dp 来记录字符串的子串是否为回文串。 dp[i][j] 表示字符串从索引 i 到索引 j 的子串是否为回文串，
如果是回文串则为 true，否则为 false。

• 1、初始化一个二维数组 dp，其中 dp[i][i] = true，表示单个字符一定是回文串。
• 2、对于长度大于1的子串，如果s[i]等于s[j]且dp[i+1][j-1]是回文子串，则dp[i][j]也是回文子串。（对称）
• 3、在遍历过程中，记录最长的回文子串的起始和结束位置。
• 4、返回最长回文子串。

Java实现

public class LongestPalindromeSubstringDP {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0;
        int end = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i][i] = true; // 单个字符一定是回文串
        }
        // 先枚举子串长度
        for (int len = 2; len <= n; len++) {
            // 枚举左边界
            for (int i = 0; i <= n - len; i++) {
                // 由 len 和 i 可以确定右边界，即 j - i + 1 = len 得
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && (len == 2 || dp[i+1][j-1])) {
                    dp[i][j] = true;
                    //当找到更长的回文串的时候，才需要更新start和end
                    if (len > end - start + 1) {
                        start = i;
                        end = j;
                    }
                }
            }
        }
        
        return s.substring(start, end + 1);
    }

    public static void main(String[] args) {
        LongestPalindromeSubstringDP solution = new LongestPalindromeSubstringDP();

        // Test case 1
//        String s1 = "babad";
//        System.out.println(solution.longestPalindrome(s1));

        // Test case 2
        String s2 = "cabdbad";
        System.out.println(solution.longestPalindrome(s2));
    }
}

时间空间复杂度

• 时间复杂度：遍历了一次二维数组dp，时间复杂度为O(n^2)，其中n为字符串s的长度。

• 空间复杂度：使用了一个二维数组dp，空间复杂度为O(n^2)。