5.最长回文子串

给定一个字符串s,找出其中最长的回文子串。可以假定s的最大长度为1000.

比如:

输入:”babad”

输出”bad”

输入:abcdedcf

输出:cdedc

python动态规划实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def longestPalindromeDp(s):  
dp = [[0]*len(s) for _ in range(len(s))]
left, right, length = 0, 0, 0

for i in range(len(s)):
for j in range(i):
if s[i] == s[j] and (i - j < 2 or dp[j+1][i-1]):
dp[j][i] = 1
if i - j + 1 > length:
length = i - j + 1
left = j
right = i
dp[i][i] = 1

return s[left:right+1]

if __name__ == "__main__":
s = "abcdedcf"
print(longestPalindromeDp(s))