[리트코드(LeetCode)] 5번 Longest Palindromic Substring

문제

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

가장 긴 팰린드롬(거꾸로 읽어도 똑같은 문장이나 단어) 부분 문자열을 출력하라는 문제다.

예시

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 문자열에서 특정 위치에서 확장하는 함수 정의
        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]
        
        # 문자열 길이가 2 미만이거나 팰린드롬인 경우
        if len(s) < 2 or s == s[::-1]:
            return s

        result = ''
        for i in range(0, len(s) - 1):
            # 현재 위치에서 짝수, 홀수 길이로 확장한 팰린드롬 중 가장 긴 문자열 반환
            result = max(result, expand(i, i+1), expand(i, i+2), key=len)
        
        return result

 

- 문자열에서 특정 위치를 중심으로 확장하는 형태로 풀어준다.

(책에서 투 포인터가 슬라이딩 윈도우처럼 계속 앞으로 전진해나간다..라고 하는데 이 부분은 더 배우고 연습해봐야 할 것 같다.)

 

* 예시 1번에서 "aba"가 나와도 된다고 했는데, max() 함수는 여러 항목이 최대값이면 처음 만난 항목을 반환해주므로 순서를 다르게(result = max(expand(i, i+1), expand(i, i+2), result , key=len)) 하면 "bab"가 아닌 "aba"가 나오는 것을 확인 할 수 있다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview