리트코드(LeetCode) 5번 가장 긴 팬린드롬 부분 문자열(Longest Palindromic Substring)

---

풀이 

두 포인터가 중앙을 중심으로 확장하는 형태의 풀이

 

우선 확장은 팰린드롬의 길이가 홀수인지 짝수인지에 따라 달라진다.

이 이야기를 하기 전에 우선 확장(expand) 함수를 만들어보자

 

 

 

expand 함수 코드

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

while문은 조건이 참일 경우 지속적으로 실행되는 조건문임으로 위의 3가지의 조건중 하나라도 거짓이 되면 

• left -= 1
• rihgt += 1

이 실행되지 않는다.

 

 

 

예외처리

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

예외처리를 통한 필터링으로 전체적인 풀이 속도 향상에 큰 도움이 될 수 있다.

문자열의 길이가 2보다 작을 때 즉 한글자이거나 문자열이 없는 경우, 그리고 전체 문자열 자체가 팰린드롬인 경우는 체크할 필요가 없으므로 예외처리를 해준다.

 

 

 

 

실행 부분

result = ''
for i in range(len(s)):
    result = max(result, expand(i, i), expand(i, i + 1), key = len)
return result

처음 말했던 전체 문자열의 길이가 홀수인지 짝수인지에 따라 확장이 달라진다는 코드가 여기서 구현된다.

팬린드롬은 'aa'처럼 짝수일 때도 있고 'aba'처럼 홀수일 때도 있다. 따라서 홀수와 짝수를 따로따로 확장하여 max로 비교해주어야 한다.

이 경우 팰린드롬이 홀수이면 동일한 지점에서 시작하게 되고 짝수이면 i와 i+1에서 시작하게 된다.

그렇게 점점 양쪽으로 expand 해 가며 체크한다.

 

예를 들어 문자열 s가 '1 2 3 4 5 4 3 2 1'인 경우 for문으로 점차 나아가다가 i가 5의 인덱스에 도착했을 경우 즉 i가 4(5의 인덱스)인 경우 expand(i, i) -> expand(4, 4)가 발동하여 '4 5 4' -> '3 4 5 4 3' -> '2 3 4 5 4 3 2' 순으로 점차 확장되게 된다.

이 경우 expand(i, i+1)는 max에 의해 자연스레 무시된다.

 

 

 

 

 

전체 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            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]:
            return s
    
        result = ''
        for i in range(len(s)):
            result = max(result, expand(i, i), expand(i, i + 1), key = len)
        return result