寻找字符串的最长回文

[编程题]寻找字符串的最长回文

热度指数：860 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一个字符串，请找出该字符串的包含的最长回文子字符串
比如，输入babcd，输出bab
输入abbc，输出bb

输入描述:

只包含a-z的的字符串

输出描述:

入参的最长回文子字符串

示例1

输入

babcd

输出

bab

算法知识视频讲解

Python

林某人

动态规划方法--改进暴力全子串判断
状态方程：

$图片说明$ 表示字符串s[i:j+1] 出是否为回文子串的判断，T or F

转态转移方程

$图片说明$
又考虑到，长度为2时的回文子串 $图片说明$ 超了范围，所以限定 j-2 > i
最终状态转移方程为：
$图片说明$

s = input()
n = len(s)
if n <= 1:
    print(s)
else:
    p = [[False for _ in range(n)] for _ in range(n)]
    maxlen = 1
    maxsstr = s[0]
    for r in range(1,n):
        for l in range(r):
            if s[l] == s[r] and (r-l<=2 or p[l+1][r-1]):
                p[l][r] = True
                length = r - l +1
                if length > maxlen:
                    maxlen = length
                    maxsstr = s[l:r+1]
    print(maxsstr)

发表于 2019-09-15 00:45:58 回复(0)