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

示例 1：

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

示例 2：

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

提示：

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

思路

不难发现，当到构成一个回文子串时，到一定也构成一个回文子串。若表示到的子串长度，那么状态转移方程为： 但是本题并不需要求最长的子串长，而是求下标。所以我们让dp[i][j]表示i和j之间是否构成回文子串。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;
        int max = 0;
        int x = 0, y = 0;

        // dp[i][j]表示从s[i]到s[j]是不是一个回文字符串
        boolean[][] dp = new boolean[len][len];
        // 只有一个字符一定是回文
        for (int i = 0; i < len; i++) dp[i][i] = true;

        // 根据子串长度循环 
        for (int l = 2; l <= len; l++) {
            // i表示左边界
            for (int i = 0; i < len - l + 1; i++) {
                // j表示右边界
                int j = i + l - 1;
                if (s.charAt(i) == s.charAt(j) && (dp[i+1][j-1] || l == 2)) {
                    dp[i][j] = true; 
                    if (l > max) {
                        x = i; y = j;
                        max = l;
                    }
                    
                }
            }
        }
        return s.substring(x, y + 1);
    }
}

复杂度

  • 时间复杂度：。
  • 空间复杂度：。