[2024] day 144. leetcode 131. Palindrome Partitioning

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 22일 (수)
Leetcode daily problem

131. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/?envType=daily-question&envId=2024-05-22

Problem

문자열 s가 주어질 때 문자열의 하위 문자열이 회문(palindrome)이 되는 하는 s의 가능한 모든 회문(palindrome) 반환한다.

회문은 앞으로나 뒤로 읽나 같은 문자열을 의미한다.

Solution

Backtracking + DP

모든 부분 문자열이 회문(palindrome)인 부분 문자열들로 분할하는 방법을 찾는 문제로 일단 주어진 문자열에 해당하는 모든 분할을 backtracking으로 시도하고, 유효한 회문 분할만 결과에 업데이트 하는 방식으로 탐색한다.

Code

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        
        def is_palindrome(sub):
            return sub == sub[::-1]
            
        def backtracking(idx, sub):
            if idx == len(s):
                subsets.append(sub[:])
                return
            
            for j in range(idx+1, len(s)+1):
                substring = s[idx:j]
                if is_palindrome(substring):
                    backtracking(j, sub+[substring])
        
        
        subsets = []
        backtracking(0, [])
        return subsets

Complexicity

시간 복잡도

문자열의 모든 가능한 분할을 탐색하므로 backtracking에서의 시간복잡도는 문자열 길이 n에 대해 최악의 경우 O(2^n) 이다. 문자열의 각 문자가 분할되거나 분할되지 않는 모든 경우롤 고려하기 때문이다.

회문 검사에서의 시간은 O(n) 이 소요되는데, 회문 검사는 백트래킹 호출 수 마다 수행되므로 전체 시작 복잡도는 O(n*2^n) 이다.

공간 복잡도

재귀 호출의 최대 깊이는 문자열 길이 n 에 비례하므로 재귀 호출 스택의 공간 복잡도는 O(n) 이다.
최악의 경우 문자열의 각 문자마다 분할이 가능한 경우가 생겨 배열의 크기가 O(2^n)이 일 수 있고, 각 분할의 평균 길이는 n/2가 될 수 있어 전체 공간 복잡도는 O(n*2^n) 이다.