我正试图解决leetcode上的Longest Palindromic Substring问题。问题陈述如下:
给定字符串S,在S中找到最长回文子串,可以假定S的最大长度为1000。
例子:
Input: "babad"
Output: "bab"
注:“ABA”也是一个有效答案。
例子:
Input: "cbbd"
Output: "bb"
我提出了以下解决方案(包括一些测试用例):
import pytest
class Solution:
def longestPalindrome(self, s):
candidate = ""
longest = ""
contains_palindrome = False
for i, char in enumerate(s):
if i == 0:
candidate = char
elif i == 1:
if s[1] == s[0]:
candidate = self.get_palindrome(s, start=0, end=1)
elif i >= 2:
if char == s[i-1]:
candidate = self.get_palindrome(s, start=i-1, end=i)
elif char == s[i-2]:
candidate = self.get_palindrome(s, start=i-2, end=i)
if len(candidate) > len(longest):
longest = candidate
return longest
@staticmethod
def get_palindrome(s, start, end):
palindrome = s[start:end+1]
while end < len(s) - 1:
if s[end+1] == s[start] and Solution.all_same(palindrome):
end += 1
palindrome += s[end]
else:
break
while (start > 0) and (end < len(s) - 1):
start -= 1
end += 1
if s[start] == s[end]:
palindrome = s[start] + palindrome + s[end]
else:
break
return palindrome
@staticmethod
def all_same(items):
return all(item == items[0] for item in items)
def test_1():
assert Solution().longestPalindrome("babad") == "bab"
def test_2():
assert Solution().longestPalindrome("cbbd") == "bb"
def test_3():
assert Solution().longestPalindrome("abba") == "abba"
def test_4():
assert Solution().longestPalindrome("a") == "a"
def test_5():
assert Solution().longestPalindrome("ccc") == "ccc"
def test_6():
assert Solution().longestPalindrome("aaaa") == "aaaa"
def test_7():
assert Solution().longestPalindrome("aaabaaaa") == "aaabaaa"
if __name__ == "__main__":
pytest.main([__file__])
问题是我收到一个“超过时间限制”错误:
我的理解是,该算法的时间复杂度为O(n ^ 2),因为每个字符都检查一个可以长达n个字符的回文。在leetcode的解决方案中也有o(n^2)算法(在java中)。
我猜时间限制对python来说有点太严格了,它比java慢。还是我错过了什么,我的解决方案的时间复杂度实际上大于O(n ^ 2)?
最佳答案
您失败的测试字符串似乎只包含a这是最坏的情况,它实际上是o(n 3)而不是o(n 2),因为all_same
中还有另一个隐藏的循环。(起初,我还认为字符串上的slice操作符[:]
会做一个复制,但事实并非如此。)
您需要调用all_same
,因为您在主函数中区分了“aa”和“aba”两种情况。但不需要在循环中这样做,因为在while
中的第一个get_palindrome
循环中,您将只添加相同的字母over和oer。因此,一个快速的解决方法是只测试一次所有字符是否相同:
if Solution.all_same(palindrome):
while end < len(s) - 1:
if s[end+1] == s[start]:
end += 1
palindrome += s[end]
else:
break
现在,
all_same
操作系统运行在两个或三个字母的字符串上,速度很快。更好的解决方案根本不需要
all_same
为什么要将“aba”传递给get_palindrome
,而您只需传递“b”并让该函数完成余下的工作: elif i >= 2:
if char == s[i-1]:
candidate = self.get_palindrome(s, start=i-1, end=i)
else:
candidate = self.get_palindrome(s, start=i, end=i)
总的来说,代码看起来很不整洁,带有所有的
break
s和不必要的大小写区分为什么要将索引和palindrome
作为单独的实体保存在get_palindrome
中,而您必须保持同步?在我看来,这是一个更整洁的版本:
class Solution:
def longestPalindrome(self, s):
longest = ""
for i, _ in enumerate(s):
candidate = self.get_palindrome(s, start = i, end = i)
if len(candidate) > len(longest):
longest = candidate
return longest
@staticmethod
def get_palindrome(s, start, end):
while end + 1 < len(s) and s[end+1] == s[start]:
end += 1
while start > 0 and end + 1 < len(s) and s[start - 1] == s[end + 1]:
start -= 1
end += 1
return s[start:end + 1]
即便如此,仍有改进的余地:对于字符串“a a aa”,代码仍将考虑“aaaa”、“aaa”、“aa”和“a”。
while
中的第一个get_palindrome
将一直进行,但没有机会找到更好的命中率我们可以通过查找主函数中已存在的同一个字母的拉伸来改进此功能:class Solution:
def longestPalindrome(self, s):
longest = ""
i = 0
l = len(s)
while i < l:
end = i
while end + 1 < l and s[end + 1] == s[i]:
end += 1
candidate = self.get_palindrome(s, i, end)
if len(candidate) > len(longest):
longest = candidate
i = end + 1
return longest
@staticmethod
def get_palindrome(s, start, end):
while start > 0 and end + 1 < len(s) and s[start - 1] == s[end + 1]:
start -= 1
end += 1
return s[start:end + 1]
这在像“abababab”这样的字符串上仍然不是理想的,但是在您的情况下应该足够快。