题目描述

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

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

题目分析

动态规划
设 dp[i][j] 表示在子串 [i, j] 是否回文，在 s[i] = s[j] 时
– j – i <= 1, dp[i][j] = true
– j – i > 1，dp[i][j] = dp[i + 1][j – 1]

由于转移方程中是 i+1，所以 i 需要倒序遍历，j 的顺序则无所谓

时间复杂度 O(n * n)，n 为 s 的长度。

Java

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

Kotlin

fun longestPalindrome(s: String): String {
    val dp = Array(s.length) { BooleanArray(s.length) }
    var start = 0
    var end = 0
    for (i in s.indices.reversed()) {
        for (j in i until s.length) {
            if (s[i] == s[j]) {
                if (j - i <= 1) {
                    dp[i][j] = true
                } else if (i + 1 in s.indices && j - 1 in s.indices) {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }
            if (dp[i][j] && j - i > end - start) {
                start = i
                end = j
            }
        }
    }
    return s.substring(start, end + 1)
}