Longest Palindromic Substring

出现 time limit exceed error, 用了dp的思路

string(i, j)
如果 i＝＝j, ref[j]=1
如果 j=i+1 && s.charAt(i)==s.charAt(j),  ref[j]=1
j>i+1      if ( s.charAt(i)==s.charAt(j) && ref[i+1][j-1]==1) ref[j]=1
理论上worst case o(n^2)的情况，有什么漏考虑了？大家指教下啊。。


否则不是palindrome

1. public class Solution {
   
2.      public String longestPalindrome(String s) {
   
3.               int bar =0; //bar 记录现在的maxmimal length;
   
4.               String ans;
   
5.               int start=0;
   
6.               if(s==null) return null;
   
7.               int len=s.length();
   
8.               if(len<=1) return s;
   
9.               int[][] ref = new int[len][len];//用来记录i到j的string是不是palindrome
   
10.               for(int i=0; i<len; i++) //初始化，长度为1的都是palindrome
    
11.                      ref[i][i] =1;
    
12.         
    
13.               for(int dif =1; dif<len; dif++)//diff 记录i, j两位数的差距
    
14.                   for(int i=0; i<len-dif; i++){
    
15.                         int j=i+dif;
    
16.                         if(dif==1 && s.charAt(i)==s.charAt(j)){
    
17.                             bar=2; start=i;
    
18.                             ref[i][j]=1;
    
19.                         }
    
20.                
    
21.                         else if(dif>1 && s.charAt(i)==s.charAt(j) && ref[i+1][j-1]==1){
    
22.                              if(dif>bar-1){ //超过最长的答案，更新结果
    
23.                                  bar=dif+1;
    
24.                                  start =i;
    
25.                              }
    
26.                              ref[i][j]=1;
    
27.                         }
    
28.                
    
29.                        else
    
30.                        ref[i][j]=0;
    
31.                 }
    
32.           return s.substring(start, start+bar);
    
33.        }
    
34. }

复制代码

算法本身没啥问题，具体实现的效率稍有些低，如果是C++的话应该能过。

你可以做3点改进：
1. 把ref的类型从int数组改成Boolean数组；
2.  将DP的三种情况统一成一种情况。（即只要s[i] 等于s[j], 那么ref[i][j] = ref[i+1][j-1]，否则ref[i][j] = false）。只要把ref预先创建得大一些就可以做到；
3.使用一维滚动数组代替二维数组ref。

考虑上述三点后，我的代码是这样的：

1.      public String longestPalindrome(String s) {
   
2.               int len = s.length();
   
3.               Boolean[] ref = new Boolean[len+1];//用来记录i到j的string是不是palindrome
   
4.               java.util.Arrays.fill(ref, true);
   
5.               
   
6.               int maxlen = 0;
   
7.               int maxi = 0;
   
8.               for (int j = 0; j < len; j++) // Beginning of the string
   
9.               {
   
10.                   for (int i = 0; i <= j; i++)
    
11.                   {
    
12.                       if (s.charAt(i) == s.charAt(j)) ref[i] = ref[i+1];
    
13.                       else ref[i] = false;
    
14.                      
    
15.                       if (ref[i]) {
    
16.                           int curlen = j - i + 1;
    
17.                           if (curlen > maxlen) {maxi = i; maxlen = curlen;}
    
18.                       }    // If ref[j] is true, then update the answer
    
19.                   }
    
20.               }
    
21.               
    
22.               return s.substring(maxi, maxi + maxlen);
    
23.                            
    
24.        }

复制代码

另外，这道题你甚至可以用O(1)内存解决：从左到右扫描一次具有'aa'或'aba'形式的字符串，这些字符串必定是palindrome的中心。然后依次判断从每个这些中心延伸出去能够扩展的最长Palindrome。取其中最大值即可。

stellari 发表于 2015-3-25 11:30
算法本身没啥问题，具体实现的效率稍有些低，如果是C++的话应该能过。

你可以做3点改进：

哇，数组长度多取一位让所有步骤统一起来，好牛啊，这一点, 没有加1的代码。。     public String longestPalindrome(String s) {
              int len = s.length();
              Boolean[] ref = new Boolean[len];//用来记录i到j的string是不是palindrome
              java.util.Arrays.fill(ref, true);

              int maxlen = 0;
              int maxi = 0;
              for (int j = 0; j < len; j++) // Beginning of the string
              {
                  for (int i = 0; i <= j; i++)
                  {
                      if (s.charAt(i) == s.charAt(j) && i<len-1) ref[i] = ref[i+1];
                      else if (s.charAt(i) == s.charAt(j) && i==len-1) ref[i] = ref[i+1];
                      else ref[i] = false;

                      if (ref[i]) {
                          int curlen = j - i + 1;
                          if (curlen > maxlen) {maxi = i; maxlen = curlen;}
                      }    // If ref[j] is true, then update the answer
                  }
              }

              return s.substring(maxi, maxi + maxlen);

       }

programming 发表于 2015-3-25 23:50
哇，数组长度多取一位让所有步骤统一起来，好牛啊，这一点, 没有加1的代码。。     public String longes ...

我先假设你这段代码中的ref = ...其实都是ref [ i ] = ...，（有可能是格式化的时候被当成斜体的开始标记了）

这两句

if (s.charAt(i) == s.charAt(j) && i<len-1) ref [ i ] = ref[i+1];
else if (s.charAt(i) == s.charAt(j) && i==len-1) ref [ i ] = ref[i+1];
               
和我原来的

if (s.charAt(i) == s.charAt(j)) ref [ i ] = ref[i+1];

是完全一致的，因为i必定<=len - 1, 所以在ref长度为len的情况下，肯定会引起OutOfBound错误。

-------------

我个人的原则是，如果能通过其他的手段把多个case归并成一个case，而可以省去if语句的话，那么通常按照前者来做。除了执行效率方面的优势外，更是出于美学上的考虑。这也是我为什么尽量不在开头做
if (len <= 0) return ...
这类语句的原因。因为如果后面的程序设计得好的话，len==0是可以和len = 其他值时同样对待的。在循环中就为了处理一个特殊情况而增加一条else if语句，还不如在一开始就除去这个特殊情况。所以多分配的那一个元素在我看来远强于增加的else if语句，当然这仅是我个人的看法。欢迎讨论。

我跑了一下， 45ms左右就能跑完，所以我感觉这个又是一个leetcode的bug
当然也是有办法可以克服的
Manacher算法，lz如果你感兴趣可以查阅一下
其实我感觉这个的要求略高

miss_snow 发表于 2015-3-25 20:06
我跑了一下， 45ms左右就能跑完，所以我感觉这个又是一个leetcode的bug
当然也是有办法可以克服的
Manach ...

你是说楼主的代码45ms可以跑完？看统计直方图的话，Java一般都在200ms以后。我认为凭目前Leetcode后台服务器的性能，Java跑这段O(n^2)的程序45ms内完成的可能性不高。除非真的用上Manacher。

C++的话45ms倒是差不多。

stellari 发表于 2015-3-25 23:27
你是说楼主的代码45ms可以跑完？看统计直方图的话，Java一般都在200ms以后。我认为凭目前Leetcode后台服 ...

我没有跑所有数据，只是单单最后tle的数据拿出来跑了跑
没有细数，不过应该是边界情况，1000个a
45ms是没问题的，就是O(n^2)

miss_snow 发表于 2015-3-25 20:06
我跑了一下， 45ms左右就能跑完，所以我感觉这个又是一个leetcode的bug
当然也是有办法可以克服的
Manach ...

看了下，太高深了，先不看🙈。

miss_snow 发表于 2015-3-25 23:38
我没有跑所有数据，只是单单最后tle的数据拿出来跑了跑
没有细数，不过应该是边界情况，1000个a
45ms是 ...

“单独拿最后的数据跑”？你是在自己的机器上跑的啊……好吧。

Leetcode上的题目在你看不见的地方其实是这样工作的：每个出题人为每种语言都要编写一段driver code，这段driver code的作用一般来说是要从一个文本文件中依次读入所有的test case，然后对读入的字符串进行parse（本题因为输入本来就是字符串所以不需这一步），调用Solution中的函数，然后进行Garbage Collection。

Leetcode上所谓的运行时间是加入了所有的overhead，字符串读取和分析，Solution中函数调用，garbage collection等等一切内容的driver code的总运行时间，并不是仅指跑Solution中这个函数的时间。TLE的意思也是说“运行所有test case的时间超过了限定值”，而不是“运行某个特定test case的时间超过了限定值”

况且，你自己的电脑本身的性能和LC的服务器分配给每个用户的资源也没有可比性啊。

stellari 发表于 2015-3-26 10:11
“单独拿最后的数据跑”？你是在自己的机器上跑的啊……好吧。

Leetcode上的题目在你看不见的地方其实 ...

所以我认为是leetcode的bug
5*10^8差不多是1s，理论上这个O(n^2)的复杂度是完全hold住的，而且应该是绰绰有余的
所以我认为lz的做法就可以了~