LeetCode-5 最长回文子串

发表于 | 分类于 | 评论数： | 阅读次数：

题目：最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

思路

  • 如何判断字符串是否为回文：

    所谓回文，就是正反都一样，在python中反转字符串非常简单，如果源字符串等于反转后的字符串，那么就可以判断为回文：

    1
    2
    3
    4
    5
    def isPalindorme(str: str):
        if str == str[::-1]:
            return True
        else:
            return False

  • 找出所有字符串

    需要遍历两次，设i为初始index，j为index+1到结尾，就可以获取所有的子串

  • 对所有子串来判断是否为回文，并记录长度，即可找到最大的回文子串

  • 对于s长度为0，或者1的，需特殊处理一下

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestPalindrome(self, s: str) -> str:
    	res_len = 0
        res = ''
        if len(s) == 0:
            return ''
        if len(s) == 1:
            return s
        for i in range(len(s)):
            for j in range(i+1, len(s) + 1):
                tempstr = s[i:j]
                if isPalindorme(tempstr):
                    if len(tempstr) > res_len:
                        res_len = len(tempstr)
                        res = tempstr
        return res

优化方法

该方法参考了官方解答中java版，思路如下：

  • 如何判断回文：
    • 随便找字符串中的一个字符
    • 如果是回文的话有两种情况：
      • 当回文字符串长度为奇数：那么该字符串左边的字符和右边的相等（从第0个开始，即自己等于自己开始，然后依次往左右扩展，得到该字符为中间的最长回文子串。）如aba。
      • 当回文字符串长度为偶数：那么左边第i个字符和右边第i+1个字符相等（从第0个开始，即自己等于下一个，然后依次往左右扩展，得到该字符为中间的最长回文子串。）如abba。
  • 从字符串s开头起遍历整个字符串，并对每个字符分别做两种回文判断，得出最大回文字符串。

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 0:
            return ''
        if len(s) == 1:
            return s
        start = 0
        end = 0
        for i in range(len(s)):
            len1 = self.expandAroundCenter(s, i, i)
            len2 = self.expandAroundCenter(s, i, i + 1)
            max_len = max(len1, len2)
            if max_len > (end - start):
                start = i - (max_len - 1) // 2
                end = i + max_len // 2
        return s[start:end + 1]

    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

如果大家有更好的方法或者思路，欢迎一起探讨。