[LeetCode]Longest Palindromic Substring

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

Longest Palindromic Substring - LeetCode

 

문제 분석

주어진 문자열에서 가장 긴 부분 palindrome(앞으로 읽어도 뒤로 읽어도 동일한)을 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_palindrome = ""

        for i in range(len(s)):
            # this if for odd length palindrome
            sub = self.check_palindrome(s, i, i)
            if len(sub) > len(max_palindrome):
                max_palindrome = sub
            
            # this is for even length palindrome
            sub = self.check_palindrome(s, i, i+1)
            if len(sub) > len(max_palindrome):
                max_palindrome = sub

        return max_palindrome

    def check_palindrome(self, s, left, right):
        # expand as long as 'left' can grow to the left.
        # and 'right' and grow to the right.
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1

        # our last matched index of left and right.
        return s[left+1:right]

접근 방법

1. 문자열의 길이만큼 순회합니다.
2. 홀수 길이인 경우를 가정한 palindrome 과, 짝수 길이인 경우를 가정한 palindrome 검사를 두번 수행합니다.
3. 두 값중 큰 값이 가장 긴 palindrome이 됩니다.

Palindrome 검사 과정

1. 순회하는 반복문 안에서 해당 위치의 인덱스를 기준점으로(짝수인 경우 i, i+1) 하여 왼쪽과 오른쪽으로 문자열 탐색을 확장해나갑니다.
2. left는 0보다는 같거나 커야하고, right는 문자열의 길이보다 작은 동안 반복하고, 확장한 왼, 오른쪽의 문자가 동일한 경우에는 탐색을 계속해나갑니다.
3. 만약 서로 다른 문자열을 만난다면 검사를 종료하고, 바로 직전의 위치까지의 문자열만을 슬라이싱하면 Palindrome을 구할 수 있습니다.

이 문제도 풀이를 시도하다 실패해 다른 사람들의 답안을 많이 참고했습니다. 그 중에서 가장 이해하기 쉬운 코드를 가져왔습니다.

 

medium 난이도의 문제를 여럿 풀다보니 두개의 포인터를 활용해서 풀이하는 해법들이 굉장히 많았습니다. 

아마도 그 이유는 최대한 반복횟수를(시간 복잡도) 줄이면서 탐색하는데 유용하게 사용하는 방법이지 않나 합니다. 조금 더 많이 풀다보면 자연스럽게 투 포인터를 활용하는 방안을 떠올려볼 수 있지 않을까 생각합니다.