5.最长回文子串 python
最长回文子串
- 题目描述
-
- 示例 1：
- 示例 2：
- 提示：
- 题目链接
- 解题思路
-
- Python 实现
- 详细解释
- 提交结果
题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
题目链接
最长回文子串
要找到字符串 s 中最长的回文子串，可以使用中心扩展法。这种方法的时间复杂度为 (O(n^2))，空间复杂度为 (O(1))，适合解决这个问题。
解题思路
-
中心扩展法：
- 回文子串的特点是从中心向两边扩展，中心可以是一个字符（奇数长度的回文）或两个字符（偶数长度的回文）。
- 遍历字符串的每个字符，以每个字符为中心，向两边扩展，找到最长的回文子串。
-
扩展函数：
- 编写一个辅助函数
expandAroundCenter，用于从中心向两边扩展，找到最长的回文子串。 - 辅助函数接受字符串
s和两个指针left和right，返回最长回文子串的起始和结束位置。
- 编写一个辅助函数
-
记录最长回文子串：
- 在主函数中，遍历字符串的每个字符，调用辅助函数，记录最长的回文子串的起始和结束位置。
Python 实现
def longestPalindrome(s