5. 最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

思路

从头开始遍历然后做中心扩展，记录最长的子串即可。

需要处理奇数和偶数的情况，在遍历时分别对 s[i] 和 s[i:i+1] 做中心扩展即可。

最终代码：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ls = len(s)
 
        def expand(l, r):
            while l >= 0 and r < ls and s[l] == s[r]:
                l -= 1
                r += 1
            return l+1, r-1
 
        start, end = 0, 0
        for i in range(len(s)-1):
            l1, r1 = expand(i, i)
            l2, r2 = expand(i, i+1)
            if r1-l1 > end-start:
                start, end = l1, r1
            if r2-l2 > end-start:
                start, end = l2, r2
        return s[start:end+1]

想得太多

expand 函数直接从 (i, i) 开始判断，这样既能处理奇数情况也能处理偶数情况。

在循环

        def expand(l, r):
            while l >= 0 and r < ls and s[l] == s[r]:
                l -= 1
                r += 1
            return l+1, r-1

中，边界条件失效时正确答案一定是 (l+1, r-1)。

看起来简单，但写起来还是踩了一些坑的。