131. Palindrome Partitioning

[zeikar]

Problem link

https://leetcode.com/problems/palindrome-partitioning/

Problem Summary

문자열이 주어질 때 적당히 잘라서 모든 substring이 팰린드롬이 되게 배열을 반환하는 문제.

Solution

백트래킹으로 하면 간단하다. 애초에 모든 substring 경우의 수를 반환해야 해서 다 탐색할 수밖에 없다.
다만 그냥 하면 중복되는 substring 체크가 많기 때문에 dp를 섞어주면 빠르게 뽑을 수 있다.

시간 복잡도는 O(2^N * N)
공간 복잡도는 O(2^N)

Source Code

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        @cache
        def is_palindrome(x, y):
            for i in range(y-x):
                if s[x+i] != s[y-i-1]:
                    return False
            return True

        @cache
        def check(idx):
            if idx == len(s):
                return [[]]

            ret = []
            for i in range(idx, len(s)):
                substr = s[idx:i+1]

                if is_palindrome(idx, i + 1):
                    palindrome = check(i+1)

                    for p in palindrome:
                        ret.append([substr] + p)

            return ret

        return check(0)