[Leetcode] 5. Longest Palindromic Substring

어제 재밌는 DP 문제를 풀고 그 맛에 취해(?) 다른 문제도 도전해봤다.

[Leetcode] 2901. Longest Unequal Adjacent Groups Subsequence II

 

DP 분류에 들어가니 제일 먼저 눈에 들어온 단어가 Palindrome 이었다.

이 유형 문제는 나올 때마다 살짝 쫄아있었는데, 주말이고 시간도 많아 도전했다.

결과는 공책 빽빽하게 한 페이지를 다 쓰고서야 풀 수 있었는데, 분발해야지😂

의식의 흐름대로 적어 본 풀이

 

 

문제 설명

문자열 s가 주어진다.
이 문자열에서 가장 긴 팰린드롬 부분 문자열을 찾아 반환하라.

팰린드롬(Palindrome)이란, 앞에서 읽든 뒤에서 읽든 같은 문자열을 말한다.
부분 문자열이란, 연속된 인덱스 구간을 의미한다.

예:

• "aba"는 팰린드롬이다.
• "abc"는 팰린드롬이 아니다.

예시

• 예제 1
  입력: s = "babad"
  출력: "bab"
  설명: "aba"도 정답이 될 수 있다. 둘 다 길이 3의 팰린드롬이다.
• 예제 2
  입력: s = "cbbd"
  출력: "bb"
  설명: 가장 긴 팰린드롬은 "bb" 하나뿐이다.

조건(제약사항)

• 1 ≤ s.length ≤ 1000
• s는 영어 알파벳 또는 숫자로만 구성된다.
• 정답이 여러 개일 경우, 아무거나 반환해도 된다.

풀이전략

우선 나는 당연히 DP로 접근했고, 1차원 dp[i] 배열을 사용했다.

그런데 풀고나서 정석 접근 방법을 찾아보니 2차원 dp[i][j] 배열을 사용해 문제를 풀었다.

우선 내 풀이 아이디어는 위에도 적혀있지만, 간단히 설명하자면 아래와 같다:

• 특정한 문자를 맨 뒤에 추가할 때, Palindrome 이 가능하려면 아래와 같은 조건이 필요하다.
  
  • 맨 처음 문자와 추가하는 문자가 같아야 한다.
  • 맨 처음 문자를 제외한 내부가 펠린드롬이어야 한다.
• DP[i] = i 번째 위치를 포함한 이후 문자열이 팰린드롬인지 여부라고 정의한다.
• i 위치 문자열을 추가할 때마다 j (0 ~ i - 1) 위치 DP 배열을 업데이트해준다.
• 이로써, 팰린드롬 가능 여부를 O(1)에 찾을 수 있다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [0 for _ in range(n)]
        dp[0] = 1
        s_idx, e_idx = 0, 0

        for i in range(1, n):
            dp[i] = 1
            for j in range(i):
                if s[j] == s[i] and dp[j + 1] == 1:
                    if e_idx - s_idx < i - j:
                        s_idx, e_idx = j, i
                    dp[j] = 1
                else:
                    dp[j] = 0

        return s[s_idx:e_idx + 1]

 

 

다른 방법이 하나 더 있다.

보통 팰린드롬 문제가 나오면 정석으로 익히고 가는 풀이라던데, 여태까지 모르고 있었다.

• 문자열 s 가 주어졌을 때, s[i] == s[j] (i < j) 이고 i + 1 ~ j - 1 이 팰린드롬이라면 i ~ j 도 팰린드롬이다.
• 따라서, j - i 를 diff 라고 정의했을 때, diff 값을 작은 수부터 확장해 나가며 두 순서쌍의 팰린드롬 여부를 확인할 수 있다.

여기서는 순서쌍을 변수로 설정했다.

개인적으로 이 부분을 읽으면서 기가 막히다고 생각했음

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = [0, 0]

        for i in range(n):
            dp[i][i] = True

        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                ans = [i, i + 1]

        for diff in range(2, n):
            for i in range(n - diff):
                j = i + diff
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    ans = [i, j]

        i, j = ans
        return s[i : j + 1]

 

결과

둘 다 실행해보면 정석 코드보다 내가 짠 코드가 아주 조금 더 빠르다.

물론 1차원 배열을 사용해 메모리도 덜 사용하는 것은 덤.