📕문제

[Leetcode] 5. Longest Palindromic Substring

문제 설명

문자열에서 가장 긴 palindromic substring(대칭 부분문자열)을 찾는 문제다.

---

📝풀이

첫 아이디어는 스택을 이용하는 것이었다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) == 1:
            return s
        stack = []
        prev = ''
        length, end = 1, 1
        for i in range(len(s)):
            if s[i] != prev:
                if len(stack) > 1 and s[i] == stack[-2]:
                    stack.pop()
                    stack.pop()
                    length += 2
                    end = i
                elif stack and stack[0] == s[i]:
                    stack.pop()
                    length += 2
                    end = i
                else:
                    stack.append(s[i])
            else:
                if stack:
                    stack.pop()
                length += 1
                end = i
            prev = s[i]
            print(stack)

        end += 1
        return s[end-length:end]

• 스택을 이용해 문자열을 하나씩 검사하며 가장 긴 대칭 부분문자열을 찾는다.

결과는 실패다.
스택을 이용하면 한번 검사해서 통과한 문자는 다시 사용되지 않는다.
예를들어'aababa'와 같은 문자열을 탐색할 때 'ababa'가 아닌 'bab'를 반환하게 되고 이를 해결할 방법이 없다.
이를 깨닫고 스택을 이용한 방법은 그만뒀다.

두 번째 아이디어는 중심 확장 방법이다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) <= 1:
            return s

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

        longest = ""
        for i in range(len(s)):
            palindrome1 = expand_around_center(i, i)
            palindrome2 = expand_around_center(i, i + 1)
            longest = max(longest, palindrome1, palindrome2, key=len)

        return longest

• left, right로부터 시작해 양쪽 끝의 문자가 같으면 양쪽으로 한칸씩 확장해 나가는 방식이다.
• 대칭 부분문자열을 두가지 경우가 존재한다.
  • 길이가 홀수인 경우 ex) aba
  • 길이가 짝수인 경우 ex) abba
• 두가지 경우를 함수를 통해 계산 후 가장 긴 부분문자열을 업데이트 한다.