leetcode-05-最长回文子串

目录

题目

leetcode原题 给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

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

示例 2:

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

示例 3:

输入:s = "a"
输出:"a"

示例 4:

输入:s = "ac"
输出:"a"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母(大写和/或小写)组成

题解:

public String longestPalindrome(String s) {
    int n = s.length();
    String res = s.substring(0, 1);
    boolean[][] dp = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    for (int j = 3; j < n; j++) {
        for (int i = 0; i < j; i++) {
            if (s.charAt(i) != s.charAt(j)) {
                dp[i][j] = false;
                continue;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            if (dp[i][j] && j - i + 1 > res.length()) {
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦