5.最长回文子串

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

比如：

输入:”babad”

输出”bad”

输入:abcdedcf

输出:cdedc

python动态规划实现:

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))