LeetCode刷题DAY 2：最长回文子串---三猫

之前刷过回文相关的题（LeetCode刷题DAY 1：回文数判断），本次再来一道跟回文相关的问题——找到最长回文子串。该题目是LeetCode热门100题之一，也是动态规划的经典问题之一，对逻辑能力还是有一定考验。

1 题目描述

输出一个字符串中的最长回文子串，如针对字符串“abacdd”输出“aba”。要注意空字符串和长度为1的字符串。

2 解题

思路一：子串遍历

把所有子串列举出来逐一进行判断即可，这个方法最为简单直接，也最容易理解，但复杂度较大。考虑到题目要求是找最长子串，因此本测试用例中优先遍历长度最长的子串，这样在出现回文子串时即可停止，不用继续遍历其他长度更小的子串。

class Solution: def longestPalindrome(self, s: str) : if len(s) >1 : t=0 result = s[0] # a表示子串长度 for a in range(len(s),1,-1): # i为子串起始位置 for i in range(0,len(s)-a+1): if s[i:i+a]==s[i:i+a][::-1]: result = s[i:i+a] t=1 break; if t==1: break; else: result = s return result

代码中有两个与字符串长度有关的for循环，还有一个判断是否回文的语句也与字符串长度有关，因此时间复杂度为O(N3)。

思路二：动态规划

动态规划第一步，是要找到可以作为转移的中间状态。这里的中间状态就是子串是否为回文串。第二步则是确定状态转移。可以发现，一个两端字符相同的字符串，如果他们中间有1个或0个字符，则该字符串为回文串（如“aa”和“aca”，两端字符都是“a”，中间没有其他字符或只有一个“c”，这两个字符串都是回文串），此时可直接判断子串状态。如果一个子串为回文串，则在他两边增加相同的字符后，新字符串仍为回文串（如“aba”左右分别增加“c”成为“cabac”后，仍为回文串），可用此关系进行状态转移。class Solution: def longestPalindrome(self, s: str) : # 长度为0或1的字符串为回文串，直接输出 if len(s)<2: return s # 建立存储状态的矩阵，默认值为False st = [[False]*len(s) for _ in range(len(s))] max_len = 0 for j in range(len(s)): for i in range(0,j+1): # 单个字符子串为回文串 if i==j: st[i][j]=True # 两端字符相同且中间有1个或0个字符为回文串 elif s[i]==s[j] : if j-i<3: st[i][j]=True else: # 两端字符相同中间字符数多于1个， # 则取决于中间子串状态 st[i][j]=st[i+1][j-1] # 其余情况的st[i][j]均为False # 当此轮为True判断长度并记录初始位置 if st[i][j]==True and j-i+1>max_len: max_len=j-i+1 start = i return s[start:start+max_len]

代码中有两个与字符串长度有关的for循环，时间复杂度为O(N2)，用到二维数组记录状态，因此空间复杂度上升为O(N2)。

---来自腾讯云社区的---三猫