一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 870|回复: 18
收起左侧

[Leetcode] Longest Palindromic Substring

[复制链接] |试试Instant~ |关注本帖
programming 发表于 2015-3-25 00:49:14 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 programming 于 2015-3-25 00:52 编辑

出现 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. }
复制代码
stellari 发表于 2015-3-25 11:30:02 | 显示全部楼层
本帖最后由 stellari 于 2015-3-25 11:34 编辑

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

你可以做3点改进:
1. 把ref的类型从int数组改成Boolean数组;
2.  将DP的三种情况统一成一种情况。(即只要s 等于s[j], 那么ref[j] = ref[i+1][j-1],否则ref[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。取其中最大值即可。




回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-3-25 20:06:31 | 显示全部楼层
我跑了一下, 45ms左右就能跑完,所以我感觉这个又是一个leetcode的bug
当然也是有办法可以克服的
Manacher算法,lz如果你感兴趣可以查阅一下
其实我感觉这个的要求略高
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-25 23:27:09 | 显示全部楼层
miss_snow 发表于 2015-3-25 20:06
我跑了一下, 45ms左右就能跑完,所以我感觉这个又是一个leetcode的bug
当然也是有办法可以克服的
Manach ...

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

C++的话45ms倒是差不多。
回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-3-25 23:38:54 | 显示全部楼层
stellari 发表于 2015-3-25 23:27
你是说楼主的代码45ms可以跑完?看统计直方图的话,Java一般都在200ms以后。我认为凭目前Leetcode后台服 ...

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

使用道具 举报

 楼主| programming 发表于 2015-3-25 23:50:32 | 显示全部楼层
本帖最后由 programming 于 2015-3-26 00:02 编辑
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 = ref[i+1];
                      else if (s.charAt(i) == s.charAt(j) && i==len-1) ref = ref[i+1];
                      else ref = false;

                      if (ref) {
                          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:51:15 | 显示全部楼层
miss_snow 发表于 2015-3-25 20:06
我跑了一下, 45ms左右就能跑完,所以我感觉这个又是一个leetcode的bug
当然也是有办法可以克服的
Manach ...

看了下,太高深了,先不看&#128584;。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-26 10:11:59 | 显示全部楼层
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的服务器分配给每个用户的资源也没有可比性啊。
回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-3-26 10:27:47 | 显示全部楼层
stellari 发表于 2015-3-26 10:11
“单独拿最后的数据跑”?你是在自己的机器上跑的啊……好吧。

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

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

使用道具 举报

stellari 发表于 2015-3-26 10:36:00 | 显示全部楼层
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语句,当然这仅是我个人的看法。欢迎讨论。



回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-26 10:40:19 | 显示全部楼层
miss_snow 发表于 2015-3-26 10:27
所以我认为是leetcode的bug
5*10^8差不多是1s,理论上这个O(n^2)的复杂度是完全hold住的,而且应该是绰 ...

抱歉我有点没跟上,5*10^8是什么数字?
回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-3-26 10:47:13 | 显示全部楼层
stellari 发表于 2015-3-26 10:40
抱歉我有点没跟上,5*10^8是什么数字?

500000000大概是单纯跑循环这个是1s吧
还是5000000有点记不太清了
但是1000000这个级别是能够hold住的
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-26 11:41:32 | 显示全部楼层
miss_snow 发表于 2015-3-26 10:47
500000000大概是单纯跑循环这个是1s吧
还是5000000有点记不太清了
但是1000000这个级别是能够hold住的

你的意思是进行5*10^8次空循环(我假设“单纯跑循环”的意思是“空循环”),无论在什么电脑上跑都需要1s?这逻辑不通啊。况且,楼主之所以TLE,主要原因不是在循环本身,而是耗在内存分配和回收上。不信的话,你可以在我的AC代码中加一句

Boolean[][] ref2 = new Boolean[len][len];

然后立刻会TLE。

这不能算OJ的bug,更多地应该说是Java的分配和垃圾回收效率比较低而已。
回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-3-26 12:22:10 | 显示全部楼层
stellari 发表于 2015-3-26 11:41
你的意思是进行5*10^8次空循环(我假设“单纯跑循环”的意思是“空循环”),无论在什么电脑上跑都需要1s ...

这个只是用来粗略判断复杂度的
正常的复杂度判断完全没问题
像Boolean[][] ref2=new Boolean[len][len]如果每个最里层的循环都要用到,完全可以放到for循环的外面操作,当作全局变量,何必放到里面?如果非要放到最内层的循环都要用到,当作局部变量,也可以重置数值,而不必new,否则都mle了,所以这个举例没有意义。或者你直接拿具体的题目说也好,至少我没遇到过两层for循环,然后每个都要重新new Boolean[len][len]这种类似的。因为如果这样子举例,单层for循环,再调用一个new总可以找到mle或者tle的方法。
你可以看看正常逻辑的代码,两层for循环之内的都要进行什么操作,就知道5*10^8是基本符合条件的。至于java效率低的问题……1k的数据量,n^2,1s跑完是完全没问题的,其他oj这种题目我做过很多,1k是很标准的O(n^2)做法。

回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-3-26 12:27:03 | 显示全部楼层
stellari 发表于 2015-3-26 11:41
你的意思是进行5*10^8次空循环(我假设“单纯跑循环”的意思是“空循环”),无论在什么电脑上跑都需要1s ...

还有一个比较“致命”的问题
如果是要考察O(n)的算法,1k的数据量太小了,至少10^6吧
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-26 13:34:51 | 显示全部楼层
miss_snow 发表于 2015-3-26 12:22
这个只是用来粗略判断复杂度的
正常的复杂度判断完全没问题
像Boolean[][] ref2=new Boolean[len][len] ...

抱歉我没有说清楚。

我的意思当然是保留楼主对2维数组的分配方式,也就是把:

Boolean[][] ref2 = new Boolean[len][len]

放到函数的最开头(所有循环之外)去。仅是这样做的话就足够引起这道题的TLE了。

回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-3-26 13:49:50 | 显示全部楼层
stellari 发表于 2015-3-26 13:34
抱歉我没有说清楚。

我的意思当然是保留楼主对2维数组的分配方式,也就是把:

10^6都会t只能说leetcode有bug了,或者oj自身的问题
楼主如果面试的时候说了1k的数据量,就只管O(n^2)说吧,1k都要O(n)真的太任性

如果你想试试其他的oj,poj绝对有比这个还难的问题,比如括号匹配,同样的数据量,java过没问题
所以我还是认为这个是leetcode的问题

给了1k的数据量,还要O(n)来解决,实在多此一举
回复 支持 反对

使用道具 举报

stellari 发表于 2015-3-26 22:35:27 | 显示全部楼层
miss_snow 发表于 2015-3-26 13:49
10^6都会t只能说leetcode有bug了,或者oj自身的问题
楼主如果面试的时候说了1k的数据量,就只管O(n^2)说 ...

Interesting.
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 14:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表