LeetCode[动态规划] - #5 Longest Palindromic Substring

原题链接：#5 Longest Palindromic SubString

 

要求：

给定一个字符串S，找出它的最长回文子串。假定S的最大长度为1000，且最长回文子串唯一

 

难度：中等

 

分析：

假定字符串s为回文字符串，则在s头部和尾部分别添加相同字符串[x]，所得结果s'=[x]s[x]也为回文字符串（论述1）。可使用动态规划方法解决此问题，递推公式便基于此特性。

创建一个布尔二维数组plain，plain[i][j]为true表示原字符串从索引i到索引j这一段子串为回文。而plain[i][j]为true的前提是s.charAt(i)与s.charAt(j)相同，且以下两个条件满足其一：

1. j-i<=2, j=i时必然成立，j-i=1则表示i与j相邻，"aa"、"bb"满足条件

2. j-i>2, 此时须plain[i+1][j-1]为true，即论述1所述

核心算法分析完毕，写一双重循环，索引i由字符串尾部向前遍历，索引j由i向后遍历，每次发现回文字符串时设置二维数组相应的值，并比较其长度是否大于当前的maxLen。若大于，则更新用于记录当前最长回文子串起始和终止位置的start和end

 

解决方案：

Java - 396ms

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

 简单测试程序

 

评论

3 楼 cywhoyi 2015-08-06  

Cwind 写道

cywhoyi 写道

有点意思，比起KMP简单得多，上次跟人介绍KMP，烦死了

这个算是比较简单的DP应用的例子了；至于KMP，阮一峰写的算法分析还是比较容易理解的

好的

2 楼 Cwind 2015-08-05  

cywhoyi 写道

有点意思，比起KMP简单得多，上次跟人介绍KMP，烦死了

这个算是比较简单的DP应用的例子了；至于KMP，阮一峰写的算法分析还是比较容易理解的

1 楼 cywhoyi 2015-08-05  

有点意思，比起KMP简单得多，上次跟人介绍KMP，烦死了