题目
给定一个字符串 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 ''
|