LeetCode 5(Longest Palindormic Substring, Python)1

1. 문제 링크

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

Longest Palindromic Substring - LeetCode

2. 문제 설명

• 문자열 s가 주어졌을 때, 가장 긴 'palindromic substring'을 반환하는 것
  • 여기서 palindromic substring이란 거꾸로 했을 때도 동일한 문자열을 의미
    • 예시1) s = "babad" 면 output = "bab", "aba"도 가능.
    • 예시2) s = "cbbd" 면 output = "bb" 

3. 처음 풀이

• 문자열 s의 인덱스 i, j에 대한 이중 for문을 돌려서
  • s의 i~j번째 문자열이 역순했을 때 동일한지 s[i:j+1] == s[i:j+1][::-1]로 확인하여
  • 맞다면 그 길이를 기존에 찾은 것보다 클 때 업데이트, 가장 큰 경우를 반환
• 결과적으로 runtime beats 5%로 좀 더 코드 개선이 필요했다

class Solution:
    def longestPalindrome(self, s: str) -> str:
        result_len = 0 #대칭인 문자열의 길이
        result ='' #대칭인 문자열
        if len(s)<2: #예외 케이스 처리
            return s
        for i in range(len(s)):
            for j in range(i,len(s)):#i<=j
                temp = s[i:j+1] #s[i]~s[j]까지의 문자열
                if temp == temp[::-1] and len(temp)>result_len: #temp와 그 역순이 같고 이전까지 찾은 대칭 문자열보다 길면
                    result = temp #결과에 대칭인 temp 문자열 저장
                    result_len = len(temp) #길이에 temp 길이 업데이트
        return result

4. 다른 사람 풀이 

• 이해하기 쉬운 직관적인 풀이
• 중앙을 정하고 좌우로 넓히며 최대 대칭 문자열을 탐색. 중앙의 기준에 대해 for 문 돌림

class Solution:
    def longestPalindrome(self, s):
        n, ans = len(s), ""
        def helper(i, j): # return max length of palindromeic substring useing i and j as center
            while i >= 0 and j < n and s[i] == s[j]:
                i, j = i - 1, j + 1
            return s[i + 1:j]
        
        for k in range(n):
            ans = max(helper(k, k), helper(k, k + 1), ans, key=len) # helper(k, k) for odd length, helper(k, k+1) for even length
        return ans

 

5. 배운 점

• 확실히 난이도가 medium인 문제들은 단순히 이중 삼중 포문으로는 time limit이 걸리거나, runtime 결과가 하위이다 
• 여기서는 동적 프로그래밍 개념을 알았으면, 좀 더 runtime 개선이 가능했을 것
  • 동적프로그래밍은, 복잡한 문제를 해결하기 위해 작은 하위 문제들로 나누어 해결하는 알고리즘 설계 기법
  • 계산된 결과를 저장하고 재활용함으로써 중복 계산을 피하고 효율적인 해결책을 찾는데 활용
  • 구현 방식
    • Top-Down (재귀 + 메모이제이션): 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하면서 중복된 계산을 피하고 메모리에 저장
    • Bottom-Up 방식 (반복문 + 테이블): 작은 문제부터 시작하여 계산한 값을 테이블에 저장하고, 이를 이용해 점진적으로 큰 문제 해결
  • 동적 프로그래밍은 최적 부분 구조와 중복되는 부분 문제들을 가지고 있는 문제들에 대해 효과적으로 사용됨: 시간 복잡도 개선