#Python查找回文字符串的算法

Question

class Solution(object): 
    def longestPalindrome(self, s):
        def algorithm(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1 

            return s[left + 1:right]
    longest = ""
    for i in range(len(s)):
        b = algorithm(i, i) 
        
        if len(b) > len(longest):
            longest = b
    return longest

solution = Solution()

print(solution.longestPalindrome('babad'))  

我如何弄清楚这段代码的算法？ 我知道什么时候“b =算法（0,0）”，然后将“b”存储在“最长”中，但是然后“b =算法（1,1）”等等，我不知道它是如何找到的答案“bab”？

Answer 1

外层函数longestPalindrome初始化一个空字符串longest来存储找到的最长回文。

然后使用循环 for i in range(len(s)) 迭代输入字符串 s 中的每个字符。

对于索引 i 处的每个字符，它调用算法函数两次：

首先，将左右都设置为 i（对于奇数长度回文）。 其次，左设置为 i，右设置为 i+1（对于偶数长度回文）。 该算法函数从左和右定义的中心执行回文扩展，同时这些位置的字符相等。然后返回扩展后的回文。

函数将得到的回文串的长度与当前最长的回文串（最长）进行比较。如果新获得的回文数较长，则更新最长的回文数。

迭代完所有可能的中心后，函数返回找到的最长回文。