5. 最长回文子串

categories: [Blog,Algorithm,mid]

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) {
            for (int i = 0; i + len < n; ++i) {
                int j = i + len;
                if (len == 0) {
                    dp[i][j] = true;
                } else if (len == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && len  > ans.length()-1) {
                    ans = s.substring(i, i + len + 1);//[) 左开右闭 长度是 j-i=len. 
                }
            }
        }
        return ans;
    }