不得不夸一下俺的LD,兼发10个包子 (转载)# Stock
u*l
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
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
