5. Longest Palindromic Substring 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: In
5. Longest Palindromic Substring
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" 思路：该题中动态规划并不是最优解，但却是一个较容易理解的思路设dp[i][j]是一个布尔值，且其意味着字符串s第i位到第j位截取出来的片段是否为回文。即 if dp[i][j] == True: s[i:j+1] 为回文关键思路：如何判定dp[i][j]是True?当dp[i+1][j-1] == True 并且s[i] == s[j]时， dp[i][j] = True解释一下：为了知道s[i:j+1]是否是回文首先,s[i] 必须等于s[j]，首尾必须呼应，这是规矩其次只要s[i+1:j+1-1]是回文，那两边同时加上一样的字符的s[i:j+1]也必定是回文.那么如何知道s[i+1:j+1-1]是回文？同样需要两个条件:s[i+1] == s[j-1] and s[i+1+1:j+1-1-1]那么如何知道s[i+2:j-1]是回文？....dp就可以开始规划了:class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ l, r = 0, 0 dp = [[False for i in range(len(s))] for j in range(len(s))]#创造动态表 for gap in range(len(s)):#跨度从最小的0开始判定 for i in range(len(s)-gap): j = i+gap dp[i][j] = (j-i <=1 or dp[i+1][j-1]) and s[i] == s[j]#为了避免out of range, 长度小于等于2且首尾相等的字符串直接判定为True if dp[i][j] and j-i+1 > r-l:#如果长度大于原记录，则把左右坐标替代 l,r = i, j return s[l:r+1]