5. 最长回文子串

5. 最长回文子串

难度中等 3273

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

示例 1：

输入：s = “babad”

输出：“bab”

解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”

输出：“bb”

示例 3：

输入：s = “a”

输出：“a”

示例 4：

输入：s = “ac”

输出：“a”

    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int len = 0; len < n; ++len) &#123;
            for (int i = 0; i + len < n; ++i) &#123;
                int j = i + len;
                if (len == 0) &#123;
                    dp[i][j] = true;
                &#125; else if (len == 1) &#123;
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                &#125; else &#123;
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                &#125;
                if (dp[i][j] && len  > ans.length()-1) &#123;
                    ans = s.substring(i, i + len + 1);//[) 左开右闭 长度是 j-i=len.
                &#125;
            &#125;
        &#125;
        return ans;
    &#125;