LeetCode Shortest Palindrome

zkb2008116 发表于 2015-7-29 04:22
第一个是找到末尾往中间走，第二个是找到中间往两边走，不是一样的么。。

你怎么非关心这个。。你的关注点偏了，这题有更低复杂度的解，这个暴力解也就没有关注的价值。建议你了解下这俩概念：复杂度、程序调优
leetcode的关注点基本都在复杂度上，所以不要纠结任何代码细节，那都是程序调优的范畴。
复杂度首先要优化，然后再考虑代码细节的事。如果给个长度100万的字符串，这两个程序可以跑到天荒地老，没一个能过的。
建议别纠结这个，琢磨出O(N)的解法，你就不需要这俩了。

zkb2008116 发表于 2015-7-29 05:48
就算是dp找 palindrome 这一步也得要O(N^2)吧， O(N)暂时还做不出来。。。。

这些hard难度的题，每题都可以用暴力方法AC掉，然而那样对自己并没有提高
要尽力找出最优解，这个过程本身就是学习啊，我做这题时，也是琢磨了将近半天，到了半夜才突然有想法，然后把O(N)的算法写出来了。

你可以先试着想出 Longest Palindromic Substring 和 Implement strStr()这两题，这两题的O(N)算法都搞懂了，这题也就没问题了。

超时不代表运行时间无穷大，比如运行时限制在2000ms，那么你1999ms也能AC，2002ms就超时了。这俩暴力算法道理是一样的，所以差别只在于常系数。
常系数这东西，快的和慢的可以差到数百倍之多，对运行时间有显著影响的。所以同复杂度的算法，写法不好的超时，写法好的通过很正常。

这俩都是暴力算法，所以如果第二个能AC，估计也是几百甚至上千毫秒吧？

这题有两个O(N)算法，楼主琢磨一下？其中一个思想略难，实现简单，一个思想简单，实现麻烦。

一堆aaaaaaaa...aaaaaaaaaaaaaa是字符串算法的常见bad case，更常见的是这个aaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaab

zkb2008116 发表于 2015-7-29 03:21
问题是为什么第一种算法就超时，第二种就AC啊？

第一种算法时间大概是第二种的两倍，你注意代码中的下标从哪儿开始。
暴力算法就别纠结这些了，反正写这个是通过不了面试的。