Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example:
Input: "cbbd" Output: "bb"
动态规划法：以"ababae"为例：
1 class Solution(object): 2 def longestPalindrome(self, s): 3 """ 4 :type s: str 5 :rtype: str 6 """ 7 sLength=len(s) 8 begin=0 9 length=0 10 table=[] 11 for i in range(sLength): 12 tem=[] 13 for j in range(sLength): 14 tem.append(0) 15 table.append(tem) 16 17 for i in range(sLength): 18 table[i][i]=1 19 20 for i in range(sLength-1): 21 if s[i]==s[i+1]: 22 table[i][i+1]=1 23 begin=i 24 length=1 25 26 for tem in range(1,sLength): 27 for i in range(sLength-tem): 28 j=i+tem 29 if (s[i]==s[j] and table[i+1][j-1])==1: 30 table[i][j]=1 31 length=tem 32 begin=i 33 34 return s[begin:begin+length+1]
Leetcode5：Longest Palindromic Substring@Python
原文：http://www.cnblogs.com/mzct123/p/6091226.html