题目

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

1
2
输入: "cbbd"
输出: "bb"
  • 字符串
  • 动态规划

解法

遍历所有字符串子串进行逐位比较

取出所有字符串子串再进行逐位比较,不用想肯定超时。

  • 时间复杂度:$O(n)=n^3$
  • 空间复杂度:$O(n)=n$
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def longestPalindrome(self, s: str) -> str:
sLength = len(s)
if sLength == 0:
return ''
for length in range(sLength, 0, -1):
for start in range(0, sLength-length+1):
subStr = s[start: start+length]
for i in range(0, length//2):
if subStr[i] != subStr[-i-1]:
break
else:
return subStr

遍历所有字符串子串进行字符串比较

和上面的方法类似,只是现在不比较每个位置了,而是比较字符串。

  • 时间复杂度:$O(n)=n^2$
  • 空间复杂度:$O(n)=n$
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestPalindrome(self, s: str) -> str:
sLength = len(s)
for length in range(sLength, 0, -1):
for start in range(0, sLength - length + 1):
subStr = s[start: start + length]
if subStr == subStr[::-1]:
return subStr
return ''

# runtime:4284 ms
# memory:13.5 MB