Question:
Given a string s, return the longest palindromic substring in s.
Example1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example2:
Input: s = "cbbd"
Output: "bb"
Mentality:
这道题可以用中心扩散法来解,依次判断我们子串所能达到的最远边距。但是要注意:我们的子串分为奇数长度和偶数长度两种情况,根据这两种情况,我们要做不同的处理。
Code:
class Solution: def longestPalindrome(self, s: str) -> str: start = 0 end = 0
for i in range(len(s)): left1, right1 = self.expendaroundcenter(s, i, i) left2,
right2 = self.expendaroundcenter(s, i, i+1) if right1 - left1 > end - start:
start, end = left1, right1 if right2 - left2 > end - start: start, end = left2,
right2 return s[start: end + 1] def expendaroundcenter(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right +=
1 return left + 1, right - 1
Result:
可以发现,上述结果还存在可以优化的空间,于是我去学习了一下大佬们的代码,在这分享
Code:
class Solution: def longestPalindrome(self, s: str) -> str: res = '' for i in
range(len(s)): start = max(0, i-len(res)-1) temp = s[start:i+1] if temp ==
temp[::-1]: res = temp else: temp = temp[1:] if temp == temp[::-1]: res = temp
return res
Result:
快了将近十倍。。但是我感觉思路差不多,他的判断很巧妙。