[LeetCode] 5. Longest Palindromic Substring

1. 문제

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

Longest Palindromic Substring - LeetCode

2. 접근 방법

일단 문제는 주어진 문자열 내에 존재하는 가장 긴 팰린드롬 부분 문자열을 찾으면 됩니다.

 

팰린드롬은 앞뒤가 같은 문자인데요, 예를 들면 "aba"와 같이 앞에서 봐도, 뒤에서 봐도 같은 문자열을 말합니다

 

팰린드롬의 종류에는 "ababa" 혹은 "bbbb" 와 같이 홀수 ver, 짝수 ver이 존재한다는 것을 유념해서 풀면 풀 수 있습니다요

 

제가 사용한 방법은 "중앙을 중심으로 슬라이딩 윈도우" 형태로 풀이한 것인데요

 

백준에 비슷한 문제가 존재하는데, 번호가 기억이 안나네용 

 

1. 가장 먼저 해야할 것은 주어진 문자열의 길이가 1일 때, 혹은 주어진 문자열 자체가 이미 팰린드롬일 때 -> 자기자신을 return하고 바로 끝냅니다.

 

2. 1의 경우가 아니라면 이제 슬라이딩 해가면서 풀어야합니다.

슬라이딩 하는 함수를 만들어서, 확인할 왼쪽, 오른쪽 idx를 지정해줍니다.

그리고 왼쪽 오른쪽 문자가 같으면 계속해서 확장을 해나가는 거죠.

 

근데 여기서 주의해야할 점은 위에서 언급했던 것처럼 팰린드롬이 홀수ver, 짝수ver이 있다는 것입니다

 

그걸 유의해서 풀면 됩니다. 

 

저같은 경우에느 ㄴmax를 사용해서 기존의 팰린드롬과 홀수ver, 짝수ver를 비교를 했는데여

max의 key 인자를 사용해서 length 기준으로 가장 긴 것을 골랐습니다.

3. 코드

python

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-1]:
                left -= 1
                right += 1
            return s[left+1: right-1]
        
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ''
        for i in range(len(s) - 1):
            result = max(result, 
                         expand(i, i+1), 
                         expand(i, i+2), 
                         key=len)
        return result

4. 마치며

알고리즘 문제를 풀면서 중첩함수를 처ㅡㅁ 써봤다ㅋ ..

그리구 max의 key인자도 처음 써봤슴다 

 

하하하