Question source

Given a string s, return the longest palindromic substring in s.

解题思路

回文字符串性质1：如果一个字符串是回文，那么其子字符串s[1:-1]也是回文。

回文字符串性质2：回文字符串的总长度有奇偶之分，例如 abba 和 aba 。

我们可以遍历一遍字母及其下标，寻找是否有比string（已知的最长回文）更长的回文。具体如下。

根据性质1，当我们找到了较长回文时，我们必须找到了较短的子回文。较短的子回文，我们可以通过遍历字母找到，那如何找到较长的回文呢？

考虑性质2，所以每次遍历判断2种情况，去覆盖子回文所有可能产生长回文的情况。例如，当s = szabccbaerc， 当找到子回文 bccb 时，我们应该将 abccba (比子回文长度长2) 和 bccba (比子回文长度长1) 作为候选 1 和 2， 判断是否他们为回文。如果是，更新回文，也确保回文长度变长。从而既考虑了性质1， 也考虑了性质 2。

遍历完字母后，我们返回的string便为最长回文字符串。

实现

判断回文的条件：str==str[::-1]

Complexity

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestPalindrome(self, s: str) -> str:
        string = ''
        for i in range(len(s)):
            start = max(0,i-len(string)-1) # 确保候选1长度比string长2
            tmp = s[start:i+1]
            if tmp == tmp[::-1]: # 判断候选1是否是回文
                string = tmp
            else:
                tmp = tmp[1:] # 候选1去掉首节点，变为候选2
                if tmp == tmp[::-1]: # 判断候选2是否是回文
                    string = tmp
        return string

结果

本方法
Runtime 84 ms, faster than 98.83% of Python3 online submissions for Longest Palindromic Substring.
Memory Usage 14.3 MB, less than 59.41% of Python3 online submissions for Longest Palindromic Substring.

References

[1] https://b23.tv/RTTEv8