LeetCode 솔루션 분류
[6/16] 5. Longest Palindromic Substring
본문
Medium
182971084Add to ListShareGiven 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.
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 1730 ms, faster than 39.63% of Python3 online submissions for Longest Palindromic Substring.
Memory Usage: 13.9 MB, less than 60.62% of Python3 online submissions for Longest Palindromic Substring.
Memory Usage: 13.9 MB, less than 60.62% of Python3 online submissions for Longest Palindromic Substring.
class Solution:
def longestPalindrome(self, s: str) -> str:
max_len = 0
max_l = len(s)
max_r = 0
for i in range(len(s)):
l1, r1 = self.longest_palin(s, i, i)
if r1 - l1 + 1> max_len:
max_len = r1-l1+1
max_l = l1
max_r = r1
l2, r2 = self.longest_palin(s, i, i+1)
if r2 - l2 + 1 > max_len:
max_len = r2-l2+1
max_l = l2
max_r = r2
return s[max_l:max_r + 1]
def longest_palin(self, s, l, r):
while l >= 0 and r < len(s):
if s[l] != s[r]:
return l+1, r-1
l -= 1
r += 1
return l+1, r-1