python学习——leetcode第五题 Longest Palindromic Substring

科技前沿 • 2025-04-07 22:43 • 阅读 44

大家好，我是讯享网，很高兴认识大家。

Example:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

讯享网

Example:

讯享网Input: "cbbd" Output: "bb"

方法一：
采用暴力解法，两次循环判断每一个子字符串是不是回文字符串，如果是，与之前最长的进行对比。这样的话，复杂度是O(n^3)，解法如下：

class Solution(object): def longestPalindrome(self, s): n = len(s) str = '' if n == 0 or n == 1: return s for i in range(n): for j in range(i): list = s[j:i+1] if i+1-j > len(str) and list == list[::-1]: str = list return str

方法二：
中心展开法，将字符串从头扫描到尾，以该字符为中心进行判断，判断两侧的字符是否相等，如果相等就继续向外展开，直到出现不相等的或者到头为止，此时将该回文字符串的长度与之前保存的最大长度进行对比，便得到了当前最大的回文字符串。

讯享网

当然，采用该方法有一个缺陷，如果回文字符串的长度不是奇数的话，也就不存在一个对称字符中心了。因此，需要分两种情况，一种是奇数长度，如abcdcba，一种是偶数长度abccba。如果为偶数的话，只需要将中心处相同的字符串进行合并，这样就又变成了奇数。

该方法的时间复杂度为：O(n^2)

代码如下：

讯享网class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ n = len(s) lmax = 1 if n == 0 or n == 1: return s index_start = index_stop = 0 for i in range(n-1): count = 1 #abc if s[i] != s[i+1]: while (i - count) >= 0 and (i + count) < n and s[i - count] == s[i + count]: count += 1 if 2*(count-1) + 1 > lmax: lmax = 2*(count-1) + 1 index_start = i - count + 1 index_stop = i + count-1 #abbc else: count_repeat = 0 while i+1 < n and s[i] == s[i+1]: count_repeat += 1 i += 1 while (i - count - count_repeat) >= 0 and (i + count) < n and s[i - count - count_repeat] == s[i + count]: count += 1 if 2*(count-1) + count_repeat +1 > lmax: lmax = 2*(count-1) + count_repeat +1 index_start = i - count - count_repeat + 1 index_stop = i + count-1 return s[index_start:index_stop+1]

这里需要注意的是：
1.为了避免列表超出范围，for i in range(n-1) ,需要指定到n-1;

2.index_stop 的值需要注意下，如果定为index_stop = i + count ，则s[i + count] ，就超出了列表范围了。

其它方法：
方法一是比较直观暴力的，方法二是通俗易懂的，网上还有其它方法，DP方法，Manacher 线性算法，暂时就不做过多了解了。

python学习——leetcode第五题 Longest Palindromic Substring

相关推荐