最长回文子串-中等

题目描述 代码 class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ # pa_list = [] pa = pa_1 = pa_2 = [] pa_len = 0 sl = list(s) #假设回文个数奇数个，从中心到两端判断 #注意不要超出左右范围，使用for循环 #假设回文个数偶数个，最中间两个相同，逐个两端判断 if len(sl) > 1: for i in range(0,len(sl)): # if i % 2 != 0: #奇数 max_len = min(i,len(sl)-i-1) j = 1 while(j <= max_len): if sl[i-j] == sl[i+j]: # pa_list.append(sl[i - j :i + j+1]) if pa_len < len(sl[i - j :i + j+1]): pa_len = len(sl[i - j :i + j+1]) pa_1 = (sl[i - j :i + j+1]) j = j + 1 else: break for i in range(0,len(sl)-1):#i与i+1组合 max_len = min(i, len(sl) - i - 2) j = 1 if sl[i] == sl[i+1]: # pa_list.append(sl[i :i + 2]) if pa_len < len(sl[i :i + 2]): pa_len = len(sl[i :i + 2]) pa_2 = (sl[i :i + 2]) while(j <= max_len): if sl[i-j] == sl[i+1+j]: # pa_list.append(sl[i - j :i + j + 2]) if pa_len < len(sl[i - j :i + j + 2]): pa_len = len(sl[i - j :i + j + 2]) pa_2 = (sl[i - j :i + j + 2]) j = j +1 else: break if pa_1 == pa_2 ==[]:#对无回文情况，考虑返回第一个字符 pa_1 = pa_2 = sl[0] elif len(sl) == 1: pa_1 = pa_2 = sl else: pa_1 = pa_2 = [] if (len(pa_1) > len(pa_2)) : pa = pa_1 else: pa = pa_2 pa = "".join(pa) return pa

分为回文是奇数个还是偶数个两种思路，要单独考虑单个字符及两个字符的情况。 3. 官方示例代码 动态规划

class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False] * n for _ in range(n)] ans = "" # 枚举子串的长度 l+1 for l in range(n): # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置 for i in range(n): j = i + l if j >= len(s): break if l == 0: dp[i][j] = True elif l == 1: 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 l + 1 > len(ans): ans = s[i:j+1] return ans

中心扩展算法

class Solution: def expandAroundCenter(self, s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1 def longestPalindrome(self, s: str) -> str: start, end = 0, 0 for i in range(len(s)): left1, right1 = self.expandAroundCenter(s, i, i) left2, right2 = self.expandAroundCenter(s, i, i + 1) if right1 - left1 > end - start: start, end = left1, right1 if right2 - left2 > end - start: start, end = left2, right2 return s[start: end + 1]

（和我算法的思路一致，不过将回文奇数个数当作特殊的回文偶数个数的情况） 5. 总结：不懂动态规划算法