时间戳

首页 > 解决方案 > Leetcode 5 最长回文子串 (python)

python - Leetcode 5 最长回文子串 (python)

问题描述

为什么我使用此代码得到错误答案？我尝试找到所有可能的子字符串，并在将它们存储到列表后找到最长的子字符串。谢谢您的帮助！

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
            length  = len(s)
            #get all possible substrings
            combinations = [s[i:j] for i in range(length) for j in range(i+1, length+1)]

            #print(combinations)

            rev = s[::-1]
            rev_combinations = [rev[i:j] for i in range(length) for j in range(i+1, length+1)]

            #print(rev_combinations)

            pan_l = []
            for i, c in enumerate(combinations)):
                if combinations[i] == rev_combinations[i]:
                    pan_l.append(combinations[i])
            
            if pan_l:
                y = max(pan_l, key=len)
                return y
            else:
                return s[0]

标签： pythonsubstringpalindrome

解决方案

考虑字符串"ab"。这会给combinations == ['a', 'ab', 'b']. 它的反面，"ba"，给出rev_combinations == ['b', 'ba', 'a']。'a'您会看到没有一个项目在它们的确切位置匹配，尽管'b'它们都是微不足道的回文。

处理这个问题的更好方法是检查每个子字符串是否是回文：

pan_l = []
for substring in combinations:
    if substring == substring[::-1]: # this substring is a palindrome
        pan_l.append(substring)

然后你不需要rev或根本不需要rev_combinations。

推荐阅读