题目
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
难度
Medium
方法
采用动态规划的方法，dp[i][j]表示从i到j是否是回文字符。dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])，其中j > i，循环处理，逐步扩大j - i，并实时记录下回文字符的最大长度和出现的位置，循环处理完后，则可以获取字符串s中的最长回文字符
python代码
class Solution(object):
def longestPalindrome(self, s):
"""
:param s: str
:return: str
a b c b
a 1 0 0 0
b 1 0 1
c 1 0
b 1
"""
dp = [[False for col in range(len(s))] for row in range(len(s))]
length = 0
max_length = 0
start = 0
end = 0
while length < len(s):
i = 0
while i + length < len(s):
j = i + length
if length == 1 or length == 0:
dp[i][j] = (s[i] == s[j])
else:
dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])
if dp[i][j] and max_length < length + 1:
max_length = length + 1
start = i
end = j
i += 1
length += 1
return s[start:end+1]
assert Solution().longestPalindrome("abcbaabc") == "cbaabc"
