[Algorithm] LeetCode #5 - Longest Palindrome Substring
개요
LeetCode #5, Longest Palindrome Substring 문제를 풀어봅니다.
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = “babad” Output: “bab” Note: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd” Output: “bb”
Example 3:
Input: s = “a” Output: “a”
Example 4:
Input: s = “ac” Output: “a”
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters (lower-case and/or upper-case),
전체 문자열 길이가 1이거나 이미 Palindrome이면 좋습니다. expand 함수는 palindrome 감지를 하는 투 포인터를 처음 기준점에서 계속 확장해 가면서 palindrome인지 체크합니다. Palindrome이 홀수 길이인지 짝수 길이인지에 영향을 받지 않도록 투 포인터는 길이 2, 길이 3 2가지로 만듭니다. 문자열 s 전체에 대해서 체크한 후 길이가 가장 긴 palindrome을 찾습니다.
class Solution:
def longestPalindrome(self, s: str) -> str:
# whole string is palindrome -> good!,
# length of string < 2 -> already a palindrome!
if len(s) < 2 or s == s[::-1]:
return s
# detect palindrome + expand two pointer
# (i, i+1) is palindrome -> i-1 == i+2 then
# (i-1, i+2) is palindrome -> ...
# if while loop breaks, s[left+1 : right] is palindrome
def expand(left: int, right: int) -> str:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1 : right]
result = ''
# move two pointer
# start at the left end, [0,1] -> [1,2] -> [2,3] -> ...
# start at the left end, [0,1,2] -> [1,2,3] -> ...
for i in range(len(s)-1):
result = max(result, expand(i, i+1), expand(i, i+2), key=len)
return result
