LeetCode 刷题:5. 最长回文子串
2023-04-19 12:15:42
# 算法题
这题普通思路比较好想,但时间复杂度高,另一种时间复杂度低的办法比较难想。
1. 题目
标题 | 最长回文字串 |
---|---|
序号 | NO.5 |
难度 | 中等 |
标签 | 字符串 动态规划 |
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad" |
示例 2:
输入:s = "cbbd" |
提示:
1 <= s.length <= 1000
s
仅由数字和英文字母组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 代码
方法一 暴力求解
这题没有要求时间复杂度,可以使用暴力循环的方法。从长到短遍历 s
所有的子串,判断是否符合回文
的要求,第一个符合要求的字串即为最长回文子串。判断字符串是否是回文可以采用对称判断字符串方法,如果第 i 个字符与倒第 i 个字符相同,即为回文。判断的时间复杂度为 O (n),而循环的时间复杂度为 O (n2),所以整体时间复杂度为 0 (n3)。
时间复杂度 O (n3)
空间复杂度 O (1)
执行用时:6676 ms, 在所有 Python3 提交中击败了 7.49% 的用户
内存消耗:15.1 MB, 在所有 Python3 提交中击败了 53.79% 的用户
1 | class Solution: |
方法二 中心扩散法
时间复杂度 O ()
空间复杂度 O ()
执行用时:ms
内存消耗:MB
执行用时:ms
内存消耗:MB