[DSA][Backtracking] 08. Palindrome Partitioning

LeetCode 131

 

08. Palindrome Partitioning

Given a string s, split s into substrings where every substring is a palindrome.
Return all possible lists of palindromic substrings.

You may return the solution in any order.

 

[아이디어]

- 문자열을 앞에서부터 잘라가며 palindrome인지 확인하고, palindrome이면 재귀적으로 다음 부분을 탐색하며 분할을 완성하고, 반복되는 palindrome 판정은 DP 테이블로 O(1)에 확인한다.

 

 

[풀이 1] Backtracking

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res, tmp = [], []
        def isPalindrome(subStr):
            n = len(subStr)
            for i in range(n//2 + 1):
                if subStr[i] != subStr[n - i - 1]:
                    return False
            return True

        def dfs(idx):
            if idx == len(s):
                res.append(tmp.copy())
                return
            
            for i in range(idx, len(s)):
                if isPalindrome(s[idx:i+1]):
                    tmp.append(s[idx:i+1])
                    dfs(i + 1)
                    tmp.pop()
        
        dfs(0)
        return res

완전 탐색 관점에서 접근하면, 문자열의 앞에서부터 길이를 늘려가며 palindrome 여부를 확인한다. 만약 현재 부분 문자열이 palindrome이라면, 남은 문자열에 대해 재귀적으로 같은 과정을 반복한다.

재귀 함수를 구현 관점에서 정리해보면, 문자열의 현재 위치 idx를 인자로 받고 idx부터 길이를 늘려가며 substring을 검사한다. palindrome인 경우에는 tmp 배열에 추가한 뒤 재귀적으로 다음 위치를 탐색한다. 재귀 호출이 끝나면, backtracking을 위해 tmp 배열에서 마지막으로 추가한 문자열을 제거(pop)한다.

종료 조건은 idx가 문자열의 길이에 도달했을 때이다. 이때 tmp 배열에는 완성된 palindrome 분할이 들어 있으므로, 이를 res 배열에 복사하여 추가하고 재귀를 종료한다.

 

이 코드에서는 isPalindrome 메서드를 통해 부분 문자열의 palindrome 여부를 확인한다. 하지만 성능 관점에서 보면, 같은 substring에 대한 palindrome 검사가 반복적으로 수행된다. 또한, Python에서는 substring slicing을 할 때 새로운 문자열이 생성되므로, 메모리 사용 비용도 발생한다.

이러한 반복 계산을 줄이기 위해 Dynamic Programming(DP)을 활용할 수 있다. s[i:j+1]이 palindrome인지 여부가 반복적으로 필요하므로, 이를 dp[i][j] = s[i:j+1]이 palindrome인지 여부 형태의 DP 테이블로 미리 계산해 두면, 탐색 과정에서 O(1) 시간에 palindrome 여부를 확인할 수 있어 성능을 크게 향상할 수 있다.

 

 

[풀이 2] Backtracking + DP

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res, tmp = [], []
        n = len(s)

        # Initialize DP table: dp[i][j] = True if s[i:j+1] is a palindrome
        dp = [[False] * n for _ in range(n)]
        
        for subStr in range(1, n + 1): # length of substring
            for i in range(n - subStr + 1):
                j = i + subStr - 1 # ending index of substring
                if s[i] == s[j]:
                    if subStr <= 2:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1] # palindrome if inner substring is palindrome

        def dfs(idx):
            if idx == n:
                res.append(tmp.copy())
                return
            
            for i in range(idx, n):
                if dp[idx][i]:
                    tmp.append(s[idx:i+1])
                    dfs(i + 1)
                    tmp.pop()
        
        dfs(0)
        return res

미리 DP 테이블을 만들어 두면, isPalindrome(s[idx:i+1])를 매번 호출하는 대신 dp[idx][i]를 통해 O(1) 시간에 해당 부분 문자열이 palindrome인지 확인할 수 있다.

여기서 subStr은 검사할 부분 문자열의 길이를 나타내고, i는 시작 인덱스, j는 끝 인덱스이다. 부분 문자열의 길이가 subStr로 고정되어 있으므로, i는 0부터 n - subStr까지 움직이고, i가 결정되면 j = i + subStr - 1로 정해진다.

부분 문자열이 palindrome이 되려면 양 끝 문자가 같아야 한다. 길이가 2 이하인 경우에는 양 끝 문자가 같다면 자동으로 palindrome이다. 길이가 2보다 길다면, 양 끝 문자가 같고 내부 부분 문자열(끝 문자 제외)이 palindrome인 경우에만 전체 문자열이 palindrome이 된다.

 

 

⏱️ 시간복잡도

최악의 경우 모든 가능한 분할을 탐색해야 한다. 문자열의 각 위치에서 “잘라야 할지 말지”를 선택하기 때문에 가능한 분할 수는 2ⁿ이고 각 분할에서 substring 생성이나 리스트 복사 등의 작업이 필요하므로, 전체 시간복잡도는 O(2ⁿ × n) 이다.

​

🧠 공간복잡도

최악의 경우 분할의 개수는 2ⁿ이고, 각 분할의 길이가 최대 n이므로, 결과를 저장하는 데 필요한 공간은 O(2ⁿ × n)이다.