[리트코드] 5. 가장 긴 팰린드롬 부분 문자열 (Python)

Longest Palindromic Substring - LeetCode

팰린드롬이란?

뒤집어도 똑같은 값이 나오는 문자열

문제

주어진 문자열에서 찾을 수 있는 가장 긴 팰린드롬을 출력하기

과정

1. 팰린드롬인지 판별하고, 그렇다면 판별하는 구간을 한 칸씩 늘려서 더 긴 팰린드롬인지 확인하는 기능을 하는 팰린드롬 함수를 만든다. 가장 길게 만들 수 있을 때까지 구간을 늘리고, 그 팰린드롬 값을 반환한다.
2. 팰린드롬이 문자열의 어느 위치에서 시작할 지 모르기 때문에 for문을 이용해서 모든 구간을 확인한다.
3. 팰린드롬이 짝수일 때와 홀수 일 때의 최소 단위가 다르므로 (짝수: 2칸, 홀수 3칸) 두 가지 모두를 살펴본다.
4. 그 후 (max(key = len))을 사용하여 가장 긴 팰린드롬을 반환한다.
5. 예외 처리를 고려한다.
       1) 제시된 문자열 길이가 1이거나, 문자열 자체가 전체 다 팰린드롬인 경우는 문자열 전체를 다시 리턴하면 된다. 이는 팰린드롬 자체가 가지는 특성이다.
       2) [a,b] , [a,b,c] 같이 팰린드롬이 없는 문자열이 제시된 경우에는 그 문자열의 첫 번째 글자를 반환한다. 이것은 이 문제에서 특별히 제시한 예외의 경우이다.

 

입력

"babad"

출력

"bab"

 

풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def palindrom(left, right):    
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]
        result = ""
        if len(s) < 2 or s == s[::-1]:
            return s
        else:
            for i in range(len(s)-1):
                result = max(result, palindrom(i, i+1), palindrom(i, i+2), key = len)
            return result if len(result) > 0 else s[0]

 

한 줄씩 코드 해석해보기

def longestPalindrome(self, s: str) -> str:

• self를 사용하는 이유: 동일한 클래스로 생성된 여러개의 객체를 구분하기 위해서다. 각각의 객체마다 갖고있는 정보가 다르기때문에, 각 객체마다 고유한 메모리 영역을 보유하는 것이다.

def palindrom(left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left+1:right]

• 입력한 문자열의 인덱스 왼쪽 오른쪽 값을 확인하기 위한 함수
• 왼쪽 인덱스 값이 0 이상이고 오른쪽값이 문자열의 길이보다 작고 같은 단어인 경우
• 왼쪽 인덱스 -1 / 오른쪽 +1
• 점점 길이를 늘려가면서 확인 후 값 return
• 슬라이싱 문법 [start : end] start오프셋부터 end-1 오프셋(인덱스)까지
• 왼쪽 값은 -1을 해주고 오른쪽 값은 +1을 해준채로 반환되기 때문에 return값에서는 왼쪽값에만 +1을 해준다.

result = ""
if len(s) < 2 or s == s[::-1]:
    return s

• 입력 받은 문자열의 길이가 2보다 작거나 문자열과 거꾸로 출력한 문자열의 값이 같은 경우 그대로 반환

else:
    for i in range(len(s)-1):
        result = max(result, palindrom(i, i+1), palindrom(i, i+2), key = len)
    return result if len(result) > 0 else s[0]

• max(str, key=len) 문자열의 길이가 가장 큰 것을 반환한다.
• 최댓값의 길이가 두 개 이상 있을 경우 index가 가장 작은 것을 출력한다.
• palindrom(i, i+1), palindrom(i, i+2) 를 넣는 이유는 뒤집어서 같은 값이 가장 작은 경우가 2개거나 3개이기 때문
• ex) 'bb' 'bab'
• 결과 값이 0보다 작은 경우 즉, 팰린드롬이 없는 경우에는 첫번재 인덱스 값 반환