问题描述
我正在尝试解决以下问题上的
我的理解是该算法的时间复杂度为O(n ^ 2)，因为对于每个字符，它都会检查回文，最长可达n个字符.在LeetCode的解决方案中，还有O(n ^ 2)算法(在Java中).
我猜想对于Python来说时间限制太严格了，比Java慢.还是我错过了什么?我的解决方案的时间复杂度实际上大于O(n ^ 2)吗?
您失败的测试字符串似乎仅由a组成.那是最坏的情况，实际上是O(n³)而不是O(n²)，因为 all_same 中还有另一个隐藏循环.(起初，我还认为字符串上的切片运算符 [:] 会进行复制，但这不是真的.)
您需要调用 all_same ，因为您要在主函数中区分大小写"aa"和"aba".但是您不需要循环执行此操作，因为您将在 get_palindrome 中的第一个 while 循环中只在上方添加相同的字母.因此，一种快速的解决方案是测试所有字符是否仅一次相同:
如果Solution.all_same(回文):而结束<镜头-1:如果s [end + 1] == s [start]:结束+ = 1回文+ = s [结束]别的:休息 现在 all_same 操作系统可以在两个或三个字母的字符串上运行，并且很快.
更好的解决方案完全不需要 all_same .当您只需传递"b"并让该函数完成其余工作时，为什么将"aba"传递给 get_palindrome ?
elif i> = 2:如果char == s [i-1]:候选人= self.get_palindrome(s，开始= i-1，结束= i)别的:候选人= self.get_palindrome(s，开始= i，结束= i) 总体而言，该代码看起来很杂乱，带有所有 break 和不必要的大小写区别.为什么将索引和 palindrome 作为单独的实体保存在 get_palindrome 中，您必须保持同步?
以下是我认为较整齐的版本:
class解决方案:def longestPalindrome(self，s):最长="对于我来说，_枚举:候选人= self.get_palindrome(s，开始= i，结束= i)如果len(候选人)>len(最长):最长=候选人返回最长@staticmethoddef get_palindrome(s，start，end):而结束+ 1<len和s [end + 1] == s [start]:结束+ = 1启动时>0和end + 1<len和s [start-1] == s [end + 1]:开始-= 1结束+ = 1返回s [开始:结束+ 1] 即使如此，仍有改进的余地:对于字符串"aaaa"，代码仍将考虑"aaaa"，"aaa"，"aa"和"a".get_palindrome 中的第一个 while 会一直执行，但是没有机会找到更好的结果.我们可以通过在主要函数中找到相同字母的延伸来改善这一点:
class解决方案:def longestPalindrome(self，s):最长="我= 0l = len(s)而我<l:结束=我而结束+ 1<l和s [end + 1] == s [i]:结束+ = 1候选人= self.get_palindrome(s，i，end)如果len(候选人)>len(最长):最长=候选人i =结束+ 1返回最长@staticmethoddef get_palindrome(s，start，end):启动时>0和end + 1<len和s [start-1] == s [end + 1]:开始-= 1结束+ = 1返回s [开始:结束+ 1] 对于像"abababab"这样的字符串，这仍然不是理想的选择，但是对于您的情况应该足够快.
I'm trying to solve the Longest Palindromic Substring problem on LeetCode. The problem statement is:
Input: "babad"
Output: "bab"
Input: "cbbd"
Output: "bb"
I've come up with the following solution (including some test cases):
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__])
The problem is that I get a "time limit exceeded" error:
My understanding is that the time complexity of this algorithm is O(n^2), since for every character it checks for a palindrome which could be up to n characters long. In LeetCode's solutions there are also O(n^2) algorithms (in Java).
I'm guessing that the time limit is a bit too stringent for Python, which is slower than Java. Or am I missing something and is the time complexity of my solution actually greater than O(n^2)?
The test string that you failed on seems to consist of a's only. That's the worst case and it is actually O(n³) rather than O(n²), because there's another hidden loop in all_same. (At first, I also thought that the slice operator [:] on strings would do a copy, but that's not true.)
You need to call all_same, because you distinguish the cases "aa" and "aba" in your main function. But you don't need to do that in a loop, because you will be adding only the same letter over and oer in the first while loop in get_palindrome. A quick fix would therefore be to test whether all characters are the same only once:
if Solution.all_same(palindrome):
while end < len(s) - 1:
if s[end+1] == s[start]:
end += 1
palindrome += s[end]
else:
break
Now all_same os run on two- or three-letter strings and will be fast.
A better solution wouldn't require all_same at all. Why do you pass "aba" to the get_palindrome when you could just pass "b" and let that function do the rest of the work:
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)
Overall, the code looks rather untidy with all the breaks and unnecessary case distinctions. And why keep indices and palindrome as separate entities in get_palindrome, which you must keep in sync?
Here's a version that is tidier in my opinion:
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]
Even so, there's room for improvement: For the string "aaaa", the code will still consider "aaaa", "aaa", "aa" and "a". The first while in get_palindrome will go all the way, but without chance to find a better hit. We can improve this by finding stretches of the same letter already in the main function:
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]
This will still not be ideal on strings like "abababab", but should be fast enough in your case.
这篇关于在Python的字符串中找到最长的回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！