5.最长回文子串 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原文地址：https://blog.csdn.net/sysu63/article/details/143937386
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！