首页 > 代码库 > Leetcode:【DP】Longest Palindromic Substring 解题报告

Leetcode:【DP】Longest Palindromic Substring 解题报告

Longest Palindromic Substring -- HARD 级别

Question SolutionGiven a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

技术分享
经典的DP题目。

主页君给出3种解法:

1. Brute Force

GitHub代码链接

这个非常Straight Forward,就是开始节点i从0-len-1遍历一次,结束结点以i - Len-1遍历一次。每个字符串都
判断它是不是回文,判断是不是回文也可以使用递归来做。总的复杂度是
Time:O(n^3), Space:O(1)

2. DP

DP 因为是二维动态规划 
Time:O(n^2), Space:O(n^2)

技术分享
 1 public String longestPalindrome(String s) { 2         if (s == null) { 3             return null; 4         } 5          6         String ret = null; 7          8         int len = s.length(); 9         int max = 0;10         11         boolean[][] D = new boolean[len][len];12         13         for (int j = 0; j < len; j++) {14             for (int i = 0; i <= j; i++) {15                 D[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || D[i + 1][j - 1]);16                 if (D[i][j]) {17                     if (j - i + 1 > max) {18                         max = j - i + 1;19                         ret = s.substring(i, j + 1);20                     }21                 }22             }23         }24         25         return ret;26     }
View Code

请戳主页君的代码哦

解说:
状态表达式:D[i][j] 表示i,j这2个索引之间的字符串是不是回文。
递推公式: D[i][j] = if ( char i == char j) && (D[i + 1][j - 1]  ||  j - i <= 2)) 这个很好理解,跟递归是一个意思,只不过 动规的好处就是我们可以重复利用这些结果。

初始化:
D[i][i] = true;实际上也不用特别初始化,都可以套到递推公式里头。 所以主页君的代码会看起来很简单。

注意:用max记录回文长度,回文找到时,更新一下max,及结果的起始地址,结束地址。

现在重点来了,我们怎么设计这个动规才可以重复利用呢?

从这里可以看出D[i + 1][j - 1], 我们推i,j的时候用到了i+1, j-1,其实意思就是在计算i,j时,关于同一个j-1的所有的i必须要计算过。

画图如下:
1. 00
2. 00 01
         11
3. 00 01 02
         11 12
              22
3. 00 01 02 03                       
         11 12 13
              22 23  
                   33

看到上面的递推关系了吗?只要我们一列一列计算,就能够成功地利用这个动规公式。这也是动态规划的关键性设计所在。
如果你不知道如何设计,就和主页群一样,画一个图来看我们计算某值的时候,需要哪些已经有的值。如上图所示,我们需要的是i+1, j - 1,实际上就是左下角的值,这样的话我们只要一列一列计算,就能成功动态规划。
注意:一行一行计算就会失败!

所以我们的循环的设计是这样的:
for (int j = 0; j < len; j++) 
  { for (int i = 0; i <= j; i++) {

具体请参见代码,慢慢感受一下。这个才是动规的精髓咯。

 

3. 中心展开法。

这个方法其实很直观,就是从头扫描到尾部,每一个字符以它为中心向2边扩展,扩展到不能扩展为止(有不同的字符),返回以每一个字符为中心的回文,然后不断更新最大回文并返回之。

算法简单,而且复杂度为O(n^2),空间复杂度为O(1)
推荐面试使用这一种方法。据说有的公司如EBAY会拒掉动规的解法. ORZ.. 其实主页君比较心水第二种解法啊,多优美,第三种解法虽然消耗更少,但没有什么普适性。

技术分享
 1 public class Solution { 2     public String longestPalindrome(String s) { 3         if (s == null) { 4             return null; 5         } 6          7         String ret = null; 8          9         int len = s.length();10         int max = 0;11         for (int i = 0; i < len; i++) {12             String s1 = getLongest(s, i, i);13             String s2 = getLongest(s, i, i + 1);14             15             if (s1.length() > max) {16                 max = Math.max(max, s1.length());17                 ret = s1;18             }19             20             if (s2.length() > max) {21                 max = Math.max(max, s2.length());22                 ret = s2;23             }24         }25         26         return ret;27     }28     29     public String getLongest(String s, int left, int right) {30         int len = s.length();31         while (left >= 0 && right < len) {32             // when i is in the center.33             if (s.charAt(left) != s.charAt(right)) {34                 break;35             }36             37             left--;38             right++;39         }40         41         return s.substring(left + 1, right);42     }43 }
View Code


中心展开法代码

其它比较牛的解法:http://blog.csdn.net/hopeztm/article/details/7932245

Ref: http://blog.csdn.net/fightforyourdream/article/details/21309759
       http://blog.163.com/zhaohai_1988/blog/static/2095100852012716105847112/
       http://blog.csdn.net/fightforyourdream/article/details/15025663

Leetcode:【DP】Longest Palindromic Substring 解题报告