LeetCode05-阿里云开发者社区

开发者社区> 云计算> 正文

LeetCode05

简介: 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_32502811/article/details/81563189 最近在刷题,对于动态规划类的问题完全懵逼····就从LeetCode上找DP的题目专门练习一下,熟悉熟悉思路。
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_32502811/article/details/81563189

最近在刷题,对于动态规划类的问题完全懵逼····就从LeetCode上找DP的题目专门练习一下,熟悉熟悉思路。
这里还有一个动态规划背包问题的比较好的资源,请戳这里.

LeetCode05

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.


Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

貌似字符串问题中,有好多都是动态规划类问题,比如经典的最大相同子串,以及这道最长回文子串。
最开始,我想到的思路是:类似最大相同子串的方法,对于二维数组dp[i][j],i用字符串的正序,j用字符串的倒序,如果str[i] == str[j] 并且dp[i - 1] [j - 1] 不为0的话,则最长回文子串长度就是dp[i-1]+dp[j-1],对于题目提供的样例,这个方法做出来是对的,但是在测评的时候,有一个样例,“abcefcba”就不对。
所以这种思路被抛弃。
结合在discussion部分看到别人的代码,思路是这样的。dp数组为boolean类型,代表从i 到 j位置的字符串是否为回文。如果从 j 到 i 为回文子串,那么它的子问题就是str[i]==str[j]并且由j+1 到 i- 1也是回文子串。因此状态转移方程就为:

dp[i][j]=truetruefalse,ifdp[j+1][i1]=trueandstr[i]==str[j],ij<=2andstr[i]==str[j],elsedp[i][j]={true,ifdp[j+1][i−1]=trueandstr[i]==str[j]true,i−j<=2andstr[i]==str[j]false,else

代码如下:

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int max = 0;
        int start = 0;
        int end = 0;
        for(int i = 0; i < len; i++){
            for(int j = 0; j <= i; j++){
                if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i - 1])){
                    dp[j][i] = true;
                }
                if(dp[j][i] && max < (i - j + 1)){
                    max = i - j + 1;
                    start = j;
                    end = i+1;
                }
            }
        }
        return s.substring(start, end);
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章