代码git：History for 5. 最长回文子串.py - WankkoRee/LeetCodeAnswersWithPython3
这题的话，因为判断一个子串是不是回文的思路，就是往中间逼近遍历，如果左右一直都是同个字符的话，那么子串回文就成立。比如说abcba，那么刚开始判断两头a，然后是两头b，最后是中位c，都成立就说明子串确实回文。
那么这个思路就可以用动态规划的状态转移方程去表示，假设dp量dp[i][j]是表示s[i:j]是否回文，那么就可以得到dp[i][j] = dp[i+1][j-1]，当然i=j或者i+1=j就是规划的边界值，需要直接判断是否回文，比如说i=j时，那么子串就1位，必定回文，i+1=j的话只需要判断s[i]==s[j]就行。
所以根据这个思路就可以大致写出一个动态规划的递归生成dp量的脚本。
class Solution:
def __solve(self, left: int, right: int) -> bool:
if self.__dp[left][right] is None:
if left == right:
self.__dp[left][right] = True
elif left + 1 == right:
self.__dp[left][right] = self.__s[left] == self.__s[right]
else:
if self.__s[left] == self.__s[right]:
self.__dp[left][right] = self.__solve(left + 1, right - 1)
else:
self.__dp[left][right] = False
return self.__dp[left][right]
def longestPalindrome(self, s: str) -> str:
n = len(s)
self.__s = s
self.__dp = [[None for __ in range(n)] for _ in range(n)]
ms = ""
m = 0
for i in range(n):
for j in range(i, n):
if self.__solve(i, j):
l = j+1 - i
if l > m:
m = l
ms = s[i:j+1]
return ms
solution = Solution()
assert solution.longestPalindrome("babad") == "bab"
assert solution.longestPalindrome("cbbd") == "bb"
assert solution.longestPalindrome("a") == "a"
assert solution.longestPalindrome("ac") == "a"然后就成功超时了，大概想了一下，最后生成dp量的那个两重循环应该是没必要的，毕竟上面已经有递归了，那么只需要在dp量中从右上开始找，以左上到右下的路线找到第一个True的即可当作最长回文子串返回。（右上开始是因为右上表示的子串最长，可以避免过短子串的无用判断；至于左上到右下还是右下到左上的话，这个只影响存在同个长度的多个最长回文子串的返回，我因为下面测试用的样例是左上表示的子串更接近，所以就用了左上到右下，实际上不影响解题）
所以按照这个思路优化一下dp量的生成。
class Solution:
def __solve(self, left: int, right: int) -> bool:
if self.__dp[left][right] is None:
if left == right:
self.__dp[left][right] = True
elif left + 1 == right:
self.__dp[left][right] = self.__s[left] == self.__s[right]
else:
if self.__s[left] == self.__s[right]:
self.__dp[left][right] = self.__solve(left + 1, right - 1)
else:
self.__dp[left][right] = False
return self.__dp[left][right]
def longestPalindrome(self, s: str) -> str:
n = len(s)
self.__s = s
self.__dp = [[None for __ in range(n)] for _ in range(n)]
ms = ""
m = 0
for i in range(n):
for j in range(i, n):
if self.__solve(i, j):
l = j+1 - i
if l > m:
m = l
ms = s[i:j+1]
return ms
solution = Solution()
assert solution.longestPalindrome("babad") == "bab"
assert solution.longestPalindrome("cbbd") == "bb"
assert solution.longestPalindrome("a") == "a"
assert solution.longestPalindrome("ac") == "a"压线过了...
执行用时：
9052 ms, 在所有Python3提交中击败了5.00%的用户
内存消耗：23.8 MB, 在所有Python3提交中击败了5.14%的用户
通过测试用例：180 / 180
这题的话，用中心扩散应该会快很多，毕竟是针对性算法，所以也试着敲了一下。大致思路就是分奇数串和偶数串两种情况分别遍历一下每一个位置当作中位的时候最长回文子串能到哪，然后比出个最长的返回就完事。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
ms = ""
m = 0
for i in range(n):
b = True
for j in range(1, min(n-i-1, i) + 1): # 左右最多扩散几位不溢出
if s[i-j] != s[i+j]:
b = False
l = (j-1)*2+1
if l > m:
m = l
ms = s[i-j+1:i+j]
break
if b:
j = min(n-i-1, i)
l = j * 2 + 1
if l > m:
m = l
ms = s[i - j:i + j+1]
for i in range(n-1):
b = True
for j in range(0, min(n - i - 2, i) + 1): # 左右最多扩散几位不溢出
if s[i - j] != s[i+1 + j]:
b = False
l = j * 2
if l > m:
m = l
ms = s[i - j+1:i+1 + j]
break
if b:
j = min(n - i - 2, i)
l = (j+1) * 2
if l > m:
m = l
ms = s[i - j:i + j + 2]
return ms
solution = Solution()
assert solution.longestPalindrome("babad") == "bab"
assert solution.longestPalindrome("cbbd") == "bb"
assert solution.longestPalindrome("a") == "a"
assert solution.longestPalindrome("ac") == "a"确实因为针对性算法的缘故，在这题里会比动态规划快很多。
执行用时：
472 ms, 在所有Python3提交中击败了93.53%的用户
内存消耗：15.3 MB, 在所有Python3提交中击败了51.01%的用户
通过测试用例：180 / 180
Comments NOTHING