Leetcode最长回文子串解法自定义测试通过但提交失败求助

我正在重新刷Leetcode，准备重返职场成为SDE。我确信自己实现的最长回文子串解法在自定义测试用例中可以通过，但提交后却未达到预期效果，想请教这一问题的原因。

class Solution:
    def longestPalindrome(self, s: str, checked = set()) -> str:
        print(s, self.isPalindrome(s))
        if len(s) == 1 or self.isPalindrome(s):
            return s
    
        if s in checked:
            print(s, checked)
            return s[0] #shortest palindrome in s
        checked.add(s)
    
        lp2 = self.longestPalindrome(s[:-1], checked)
        lp1 = self.longestPalindrome(s[1:], checked)
        print()
    
        if len(lp1) > len(lp2):
            return lp1
        return lp2
    
    def isPalindrome(self, s:str) -> str:
        i=0
        j=len(s)-1
        while i<j:
            if s[i]!=s[j]:
                return False
            i=i+1
            j=j-1
        return True

问题原因 #

• 默认参数共享引发逻辑错误：Python函数的默认参数在定义时初始化，你用checked = set()作为默认参数，会导致所有测试用例调用共享同一个集合。多次递归后集合累积大量子串，后续调用会错误触发s in checked分支，直接返回s[0]，中断正常的最长回文查找逻辑。
• checked分支返回逻辑错误：即使子串已被检查过，直接返回第一个字符也不合理——该子串中必然存在更长的回文子串，这个返回逻辑会截断正确结果。
• 递归效率过低：这种暴力递归+简单记忆化的方式时间复杂度接近O(2ⁿ)，对于较长的输入字符串会直接超时，无法通过所有测试用例。

修复方案 #

1. 修正默认参数初始化：将默认参数改为None，在函数内部创建新集合/字典，避免跨调用共享：

def longestPalindrome(self, s: str, checked=None) -> str:
    if checked is None:
        checked = {}  # 用字典存储每个子串的最长回文结果，而非仅标记是否检查过
    # 后续逻辑调整

2. 优化记忆化逻辑：用字典缓存每个子串的最长回文结果，再次遇到相同子串时直接返回缓存值：

if s in checked:
    return checked[s]
# 计算得到lp1和lp2后，将结果存入checked
result = lp1 if len(lp1) > len(lp2) else lp2
checked[s] = result
return result

3. 替换为高效算法：推荐使用中心扩展法，遍历每个字符和每对相邻字符作为回文中心，向两侧扩展寻找最长回文，时间复杂度O(n²)，实现简单且能通过所有测试用例。

内容的提问来源于stack exchange，提问作者sib