题目

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

示例 1：

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

示例 2：

1
2
输入: "cbbd"
输出: "bb"
  • 字符串
  • 动态规划

解法

遍历所有字符串子串进行逐位比较

取出所有字符串子串再进行逐位比较，不用想肯定超时。

  • 时间复杂度：$O(n)=n^3$
  • 空间复杂度：$O(n)=n$
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestPalindrome(self, s: str) -> str:
        sLength = len(s)
        if sLength == 0:
            return ''
        for length in range(sLength, 0, -1):
            for start in range(0, sLength-length+1):
                subStr = s[start: start+length]
                for i in range(0, length//2):
                   	if subStr[i] != subStr[-i-1]:
                       	break
                else:
                    return subStr

遍历所有字符串子串进行字符串比较

和上面的方法类似，只是现在不比较每个位置了，而是比较字符串。

  • 时间复杂度：$O(n)=n^2$
  • 空间复杂度：$O(n)=n$
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestPalindrome(self, s: str) -> str:
        sLength = len(s)
        for length in range(sLength, 0, -1):
            for start in range(0, sLength - length + 1):
                subStr = s[start: start + length]
                if subStr == subStr[::-1]:
                    return subStr
        return ''

# runtime:4284 ms
# memory:13.5 MB