返回s中最长的回文子串

Question

给定一个字符串s，编写一个Python函数，该函数将返回s中最长的回文子串。回文串是正着读和倒着读都一样的字符串。例如，对于输入字符串s="babad"，函数应该返回"bab"。

Answer 1

def longest(s):
    if len(s) < 2:
        return s
    start = 0
    end = 0
    for i in range(len(s)):
        # 以i为中心扩散得到的奇数长度的回文序列的长度
        len1 = expand(s, i, i)
        # 以i和i+1为中心扩散得到的偶数长度的回文序列的长度
        len2 = expand(s, i, i+1)
        # 选一个更长的
        length = max(len1, len2)
        # 判断是否比之前更长
        if length > end - start:
            start = i - (length - 1) // 2
            end = i + length // 2

    return s[start:end+1]

def expand(s, left, right):
    '''向两端扩散'''
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # 返回此序列的长度
    return right - left - 1

s='babad'

longest(s)

输出为’bab’

Comments

输出结果为aba？