題目
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
方法
采用動(dòng)態(tài)規(guī)劃的方法，dp[i][j]表示從i到j(luò)是否是回文字符流炕。dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])，其中j > i眶熬，循環(huán)處理，逐步擴(kuò)大j - i，并實(shí)時(shí)記錄下回文字符的最大長(zhǎng)度和出現(xiàn)的位置塞关，循環(huán)處理完后，則可以獲取字符串s中的最長(zhǎng)回文字符
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"
