专栏首页share ai happiness每天一杯力扣快乐水

每天一杯力扣快乐水

题目:

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

输出示例1:

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

输出示例2:

输入: "cbbd"

输出: "bb"

在这里只提供一种解法,如果有更好的解法,私聊我~

菜鸡的我只能想出两个for循环进行暴力求解法。

我参考了一下大神的代码:

方法:动态规划

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    dp[i][j] = true;
                } else if (l == 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] && l + 1 > ans.length()) {
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        return ans;
    }
}

本文分享自微信公众号 - 1001次重燃(smile765999),作者:木东昭昭

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HBase 内部探索之旅

    写缓存,K-V在MemStore中进行排序,达到阈值之后才会flush到StoreFile,每次flush生成一个新的StoreFile。

    木野归郎
  • HTTP和HTTPS的那些事

    HTTPS 在 HTTP 与 TCP 层之间加入了 SSL/TLS 协议,可以很好的解决了上述的风险:

    木野归郎
  • 聚类算法简析(一):朴素贝叶斯算法

    朴素贝叶斯算法常用于分类与预测的问题,比如给一个1000本书进行分类,可以分为文学类,管理类,技术类,教育类等等,即算法得到的结果是一组离散的代表类别的数据。比...

    木野归郎
  • HDU-2476-String painter

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <algorithm> #include <cs...

    f_zyj
  • JVM 的运行数据区

     栈空间里存放的是局部变量表,动态链接,操作数栈,以及是方法的出口;每个栈帧都会随着方法的开始和结束相应的出栈和入 栈;

    矿泉水
  • JVM 的体系结构

     栈空间里存放的是局部变量表,动态链接,操作数栈,以及是方法的出口;每个栈帧都会随着方法的开始和结束相应的出栈和入 栈;

    用户2141593
  • 51Nod-1054-最长等差数列

    ACM模版 描述 ? 题解 额,最近不知道 51Nod51Nod 怎么了,一下子井喷了好多题,不过这个题就是 1055最长等差数列1055 最长等差数列 的一个...

    f_zyj
  • FastDFS蛋疼的集群和负载均衡(三)之上传图片测试

    用户2032165
  • Leetcode Golang 105. Construct Binary Tree from Preorder and Inorder Traversal.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88935501

    anakinsun
  • 强化学习笔记2:Markov decision process(MDP)

    我们说一个state若满足 ,则其具有马尔可夫性,即该state完全包含了历史中的所有信息。马尔科夫过程是无记忆的随机过程,即随机状态序列 具有马尔可夫属性。

    列夫托尔斯昊

扫码关注云+社区

领取腾讯云代金券