LeetCode 005 Longest Palindromic Substring

LeetCode

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

Example 1:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

Constraints:

1 <= s.length <= 1000 s consist of only digits and English letters.

题目大意：

最长回文

解题思路：

遍历每个字符，以该字符为中心，往前后比较是否回文，求最长回文

解题步骤：

N/A

注意事项：

1. 回文字符串的中心位可以为1个或2个
2. 此题求最长回文字符串，而不是其长度
3. 避免死循环，记得i -= 1, j += 1
4. Line 63 若不相等，要break，或者return[i + 1:j]和下面return一样

Python代码：

def longestPalindrome(self, s: str) -> str:
	res = ''
	for i in range(len(s)):
		tmp = self.longestPalindromeFromCenter(s, i, i)
		if len(tmp) > len(res):
			res = tmp
		if i + 1 < len(s):
			tmp = self.longestPalindromeFromCenter(s, i, i + 1)
			if len(tmp) > len(res):
				res = tmp
	return res

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

算法分析：

时间复杂度为O(n2)，空间复杂度O(1)