u***l
发帖数: 51 | 1 用 python 做的，如果用O(n^2) 的方法做，发现下面 a)的code可以过，但是 b)会超时
https://oj.leetcode.com/problems/longest-palindromic-substring/
a 和 b 中只有 function f 不一样，请问这两个到底是哪里产生的不同？谢谢。
OJ 显示超时的例子是 "aaaa...(很长) b(在靠中间的位置) aaaa(很长)"
###########################
a)
class Solution:
# @return a string
def longestPalindrome(self, s):
def f(s, p, q): # find longest palindrome centered at p and q
while p >= 0 and q < len(s) and s[p] == s[q]:
p -= 1; q += 1
return s[p + 1 : q]
res = ""
for i in range(len(s)):
res1 = f(s, i, i)
if len(res1) > len(res): res = res1
if i >= 0 and i + 1 < len(s) and s[i] == s[i + 1]:
res2 = f(s, i, i + 1)
if len(res2) > len(res): res = res2
return res
#########################################
b)
class Solution:
# @return a string
def longestPalindrome(self, s):
def f(s, p, q):
while p - 1 >= 0 and q + 1 < len(s) and s[p - 1] == s[q + 1]:
p -= 1; q += 1
return s[p : q + 1]
res = ""
for i in range(len(s)):
res1 = f(s, i, i)
if len(res1) > len(res): res = res1
if i >= 0 and i + 1 < len(s) and s[i] == s[i + 1]:
res2 = f(s, i, i + 1)
if len(res2) > len(res): res = res2
return res | n*******s
发帖数: 17267 | 2 这种题随便狗一下就能弄出一堆答案吧。
刷题我是这么看的， 现在都有飞机开了， 这些公司还在考你自行车的最佳骑法， 你
最好还都能背下来所有的路线，开个玩笑， 呵呵。 |
|
