题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
1
2
3
| 输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
|
示例 2：
解法
遍历所有字符串子串进行逐位比较
取出所有字符串子串再进行逐位比较，不用想肯定超时。
时间复杂度：$O(n)=n^3$空间复杂度：$O(n)=n$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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 ''
|
