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.
class Solution:
def longestPalindrome(self, s: str) -> str:
def expand(left: int, right: int) -> str: # 3
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
if len(s)<2 or s==s[::-1]: # 1
return s
result = ''
for i in range(len(s)-1):
# 2
result = max(result,
expand(i, i+1),
expand(i, i+2),
key=len)
return result
이 문제는 2칸짜리 윈도우, 3칸짜리 윈도우를 만들어서 왼쪽에서 오른쪽으로 이동하면서 palindrome
을 찾으면 좌/우로 확장(expand)하는 방법으로 풀면 된다.
Input 예시
"123454321"
예외 처리