LeetCode5.最长回文子串

题目来源：力扣（LeetCode）

题目描述：
给你一个字符串 s ，找到 s 中最长的回文子串。

示例1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

  

 

  
1
  
2
  
3
 

示例2：

输入：s = "cbbd"
输出："bb"

  

 

  
1
  
2
 

示例3：

输入：s = "a"
输出："a"

  

 

  
1
  
2
 

示例4：

输入：s = "ac"
输出："a"

  

 

  
1
  
2
 

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母（大写和/或小写）组成

解题思路：

Python实现
1.暴力法
暴力法始终是最简单的一种解法，但是速度方面就不尽人意。两层 for 循环遍历所有情况，找出最大的回文子串。代码提交时显示超时。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        # 将首字符作为max_str的初始值
        max_str = s[0]
        for i in range(length - 1):
            for j in range(i + 1, length):
            	# 如果s[i: j + 1]是回文子串并且长度大于len(max_str)，就将其替换
                if s[i: j + 1] == s[i: j + 1][::-1] and j - i + 1 > len(max_str):
                    max_str = s[i: j + 1]
        return max_str

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

时间复杂度：O(n³)
空间复杂度：O(1）

2.中心扩散法
根据回文串的对称性，我们可以指定它的中心进行循环，每次判断左右字符是否相等即可。

class Solution(object):
    def expandAroundCenter(self, s, left, right):
        max_len = 0
        # 退出条件：越界
        while left >= 0 and right < len(s):
            if s[left] == s[right]:
                left -= 1
                right += 1
            else:
                break
        return right - left - 1


    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        rst = s[0]
        # 遍历中心点
        for i in range(len(s) - 1):
        	# 通过expandAroundCenter方法获取最大回文串长度
        	# 奇数时，left = right = i
            odd_len = self.expandAroundCenter(s, i, i)
            # 偶数时，left = i，right = i + 1
            even_len = self.expandAroundCenter(s, i, i + 1)
            #获取最大len
            max_len = max(odd_len, even_len)
            if max_len > len(rst):
            	# 获取回文串起始下标
                begin = i - (max_len - 1) // 2
                rst = s[begin: begin + max_len]
        return rst

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

时间复杂度：O(n²)
空间复杂度：O(1）

文章来源: blog.csdn.net，作者：Dream丶Killer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_43965708/article/details/116461982