[LeetCode 해석 및 풀이] 131. Palindrome Partitioning(회문 분할)

문제 131. Palindrome Partitioning(회문 분할)

난이도 : 중간🟡 바로가기

 

문제 설명

영문

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

 

한글

문자열 s가 주어지면, 분할한 s의 모든 분할의 하위 문자열이 회문이 되도록 합니다. s 의 모든 가능한 회문 분할을 반환합니다.

 

제한조건

• 1 <= s.length <= 16
• s contains only lowercase English letters.

 

입출력 예

입력	출력
s = "aab"	[["a","a","b"],["aa","b"]]
s = "a"	[["a"]]

 

해답 및 해설

파이썬 (Python)

Backtracking

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        part = []

        def helper(i):
            if i >= len(s):
                result.append(part.copy())
                return

            for j in range(i+1, len(s)+1):
                if not isPali(i, j):
                    continue
                
                part.append(s[i:j])
                helper(j)
                part.pop()

        def isPali(i, j):
            while i < j:
                if s[i] != s[j-1]:
                    return False
                i += 1
                j -= 1
            return True
            
        helper(0)

        return result

 

인덱스부터 특정 부분까지가 회문인지 확인하고, 만약 회문이라면 그 이후 부분부터 재귀를 돌려 체크하는 방식.

 

DP(먼저 회문인 인덱스를 체크하고 만드는 방식)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def isPali(i, j):
            j -= 1
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        idx_list = [[i+1] for i in range(len(s))]
        bundle_list = [[] for _ in range(len(s))]

        for i in range(len(s)):
            for j in range(i+2, len(s)+1):
                if isPali(i, j):
                    idx_list[i].append(j)
        
        for i in range(len(s)-1, -1, -1):
            for j in idx_list[i]:
                if j == len(s):
                    bundle_list[i].append([s[i:]])
                else:
                    for bundle in bundle_list[j]:
                        bundle_list[i].append([s[i:j]]+bundle)

        print(bundle_list)
            
        return bundle_list[0]

먼저 회문이 되는 인덱스를 뽑아둔 다음, 해당 인덱스 이후 회문 분할이 되는 조합을 다 저장해두고 확인하면 더 빠르지 않을까 했는데, 이전 풀이보다 더 느렸었다. 아마 인덱스 뽑을 때 한번, 회문 분할 조합 따질 때 한번 이렇게 반복문을 두번 돌리는게 문제가 아니었나 싶다.

 

DP(회문 체크와 회분 분할 조합 확인을 동시에)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def isPali(i, j):
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        memo = dict()

        def helper(i):
            result = []
            if i == len(s):
                return []
            
            if i in memo:
                return memo[i]
            
            temp = ""
            for j in range(i, len(s)):
                temp += s[j]
                
                if isPali(i,j):
                    bundle_list = helper(j+1)
                    if not bundle_list:
                        result.append([temp])
                    else:
                        for bundle in bundle_list:
                            result.append([temp]+bundle)
            
            memo[i] = result.copy()
            return result
        
        return helper(0)

해당 방법이 셋중에서 가장 빨랐다.