Leetcode 5 最长回文子串 (python)

Question

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

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]

Answer 1

考虑字符串 "ab"。这将给出 combinations == ['a', 'ab', 'b']。它的反面 "ba" 给出 rev_combinations == ['b', 'ba', 'a']。您会看到 none 的项目在它们的确切位置匹配，即使 'a' 和 'b' 都是平凡的回文。

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

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

那么您根本不需要 rev 或 rev_combinations。

Answer 2

Jasmin 提供您的代码不正确的原因。

一个解决方法是将 rev_combinations 定义为：

#rev = s[::-1]  # Remove this line
# reverse substrings using s[i:j][::-1]
rev_combinations = [s[i:j][::-1] for i in range(length) for j in range(i+1, length+1)]

现在您的代码可以工作了。

Leetcode 5 最长回文子串 (python)

Leetcode 5 Longest Palindromic Substring (python)

python

substring

palindrome