Python递归实现最长回文子串：如何让双分支并行返回？

你代码里的核心问题是：longestPalindrome函数中，第一个return self.longestPalindrome(s[1:])会直接终止函数执行，后面的return self.longestPalindrome(s[:-1])永远无法被触发。

要让两个递归分支都运行，并且最终得到正确的最长回文子串结果，你需要先执行两个分支的递归调用，再根据结果的长度返回更优的那个——毕竟我们要找的是最长的回文子串，而非单纯“先得到”的结果。

修改后的代码 #

class Solution:
    def p(self, s: str) -> bool:
        if len(s) <= 1:
            return True
        elif s[0] != s[-1]:
            return False
        return self.p(s[1:-1])

    def longestPalindrome(self, s: str) -> str:
        if self.p(s):
            return s
        # 执行两个递归分支，获取各自的结果
        left_branch = self.longestPalindrome(s[1:])
        right_branch = self.longestPalindrome(s[:-1])
        # 返回长度更长的回文子串，长度相同时返回任意一个均可
        return left_branch if len(left_branch) >= len(right_branch) else right_branch

改动说明 #

1. 移除原代码中无效的第二个return语句，改为先调用两个递归分支并保存结果
2. 比较两个分支结果的长度，返回更长的那个——这才符合“最长回文子串”的需求
3. 保留了你原本的回文判断逻辑p函数，仅调整了递归分支的执行和结果选择逻辑

注意：这种递归方法的时间复杂度是指数级的，处理较长字符串时会非常低效。实际开发中更推荐中心扩展法、Manacher算法或动态规划来实现，但以上修改完全解决了你当前遇到的分支执行问题。

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