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;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
200. 岛屿数量 200. 岛屿数量
200. 岛屿数量难度中等 1006给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,
下一篇 
199. 二叉树的右视图 199. 二叉树的右视图
199. 二叉树的右视图难度中等 416给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。示例:输入: [1,2,3,null,5,null,4]输出: [1, 3, 4]解释:   1      
  目录