在Python的字符串中找到最长的回文 [英] Finding the longest palindrome within a string in Python

问题描述

我正在尝试解决以下问题上的

我的理解是该算法的时间复杂度为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:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer. Example:

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的字符串中找到最长的回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！