Longest Palindromic Substring

LeetCode의 Longest Palindromic Substring 문제다.

Longest Palindromic Substring - LeetCode

제목 그대로 가장 긴 회문 문자열을 찾는 문제인데 이전에 풀어봤던 Valid Palindrome 문제에서 언급했듯이 Palindrome이란 회문으로 거꾸로 뒤집어도 동일한 문자열을 의미한다. 굳이 더 설명하진 않고 그러면 문자열에서 어떻게 회문을 탐색할 수 있는지 알아보자.

 

책에서 설명하는 방법은 모든 회문은 기본적으로 두 글자, 또는 세 글자에서 시작한다는 것이다. 즉 짝수 글자의 회문과 홀수 글자의 회문이 존재할 수 있기 때문에 두 개를 따로 탐색하는 투 포인터 방법을 제안했다. 이 원리는 다음과 같다.

• "abcdcbe"라는 문자열이 있을 경우 이 문자열에서 제일 긴 회문은 "bcdcb"로 홀수 글자의 회문이다.

• 이 홀수 회문은 "cdc"에서 처음 발견된다. 리스트를 초과하지 않는 범위에서 한 글자씩 앞뒤로 늘려가며 탐색한다.

• 회문이 유지되는 동안 탐색한 후 최종적으로 얻은 회문을 기존에 얻은 회문과 비교하여 업데이트한다.

이 원리는 짝수 글자의 회문에도 동일하게 적용된다. 중요한 것은 탐색된 회문의 범위가 문자열을 벗어나지 않도록 제한해야 한다는 것이다. 이렇게 탐색된 회문 중 가장 긴 길이의 회문을 반환하면 된다. 이를 기반으로 구현한 코드는 다음과 같다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s
        
        even_palindrome = ''
        odd_palindrome = ''
        
        for index in range(1, len(s)):
            left_index = index - 1
            right_index = index
            
            if s[left_index] == s[right_index]:
                # short-circuit logic!
                while left_index >= 0 and right_index < len(s) and s[left_index] == s[right_index]:
                    # latter palindrome is not always longer than prior!
                    detected_palindrome = s[left_index:right_index+1]
                    left_index -= 1
                    right_index += 1
                    
                if len(detected_palindrome) > len(even_palindrome):
                    even_palindrome = detected_palindrome
            
            left_index = index - 1
            right_index = index + 1
            
            if right_index < len(s) and s[left_index] == s[right_index]:
                while left_index >= 0 and right_index < len(s) and s[left_index] == s[right_index]:
                    detected_palindrome = s[left_index:right_index+1]
                    left_index -= 1
                    right_index += 1
                    
                if len(detected_palindrome) > len(odd_palindrome):
                    odd_palindrome = detected_palindrome
            
        
        return max(even_palindrome, odd_palindrome, s[0], key=lambda palindrome: len(palindrome))

처음 코드를 제출하고 테스트 케이스에서 놓쳤던 점은 나중에 발견된 회문이 먼저 발견된 회문보다 항상 더 긴 것은 아니란 것이다. 그래서 지금 발견된 회문과 나중에 발견된 회문을 비교하는 로직을 추가했고 회문이 단 한 글자인 경우, 예를 들어 "ac" 같은 문자열에서는 가장 긴 회문을 "a"로 취급한다. 그런 점 때문에 마지막에 max() 함수에 비교 기준 대상으로 문자열의 첫 번째 글자를 추가했다. 홀수든 짝수든 회문이 존재한다면 최소한 한 글자는 아닐 것이기 때문에 s[0]처럼 한 글자만 추가해준 것이다.

 

책에서는 다음처럼 더 간소화된 코드의 풀이를 제공하고 있다.

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

탐색하는 로직을 expand 함수로 따로 정의해서 활용하고 있으며 마지막에 비교할 때 비교 함수인 key에 len을 전달하고 있다. 굳이 람다식으로 정의할 필요가 없이 매개변수 하나를 받아서 그 결과를 반환하는 함수를 전달해주면 된다는 점을 알 수 있었다.

 

특히 따로 한 글자짜리 회문을 추출하는 로직이 없어도 "ac" 같은 문자열에서 한 글자짜리 회문을 추출하는 것도 가능한데 이는 생긴 것과는 달리 expand(i, i+1) 호출이 홀수 글자 회문을, expand(i, i+2) 호출이 짝수 글자 회문을 담당하기 때문이다. expand 함수에서는 s[left]와 s[right-1]을 비교하기 때문에 전자는 결국 같은 글자(한 글자)를 탐색하게 된다. 그리고 탐색 범위를 늘려가면서 세 글자, 다섯 글자처럼 홀수로 증가하기 때문에 홀수 글자 회문을 담당하게 되는 것이다. 후자는 s[left]와 s[left] 다음에 있는 글자, 즉 총 두 글자를 비교하기 때문에 짝수 글자 회문을 탐색하게 된다. 얼핏 보면 간단하면서도 정교한 풀이 방법이라 할 수 있다.