[LeetCode] 5. Longest Palindromic Substring

Jadon·2021년 12월 29일
0
post-thumbnail

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.

My Solution

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"

#1

예외 처리

  • 문자열의 길이가 2보다 작으면 palindrome이 될 수 없다.
  • 뒤집어서 일치하면 별다른 코드 없이 바로 return.

#2

  • (문자열 길이 - 1)만큼 반복문 수행, i가 expand의 시작점이 되는데 i가 마지막 index면 오른쪽으로 확장이 불가능하기 때문이다.
  • 0부터 시작.
  • 2칸짜리 윈도우, 3칸짜리 윈도우에서 길이가 가장 긴 것을 result에 저장

#3

  • expand(0, 1)과 expand(0, 2), 2칸 윈도우와 3칸 윈도우가 시작됨.
  • 예시에서는 2칸 윈도우는 (1,2), 3칸 윈도우는 (1,2,3)을 잡게 됨.
  • expand(1, 2), expand(1, 3) ... expand(4, 5),
  • expand(4,6)에서 처음으로 while 조건 부합. left -= 1과 right += 1을 반복하며 좌/우로 확장.

0개의 댓글