131. Palindrome Partitioning

Palindrome Partitioning - LeetCode

문자열이 입력된다.

입력된 문자열의 연속된 부분 문자열이 모두 Palindrome(회문, 앞에서 읽어도, 뒤에서 읽어도 같은 문자열)이 되게 하는 그 결과 목록을 반환하는 문제다.

 

1. DP + DFS

from typing import *


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

        dp = [[0] * (len(s) + 1) for _ in range(len(s))]

        if len(s) == 1:
            return [[s]]
        if len(s) == 2:
            if s[0] == s[1]:
                return [[s], [s[0], s[1]]]
        for i in range(len(dp)):
            dp[i][1] = 1
        for i in range(len(dp) - 1):
            dp[i][2] = 1 if s[i] == s[i + 1] else 0

        for length in range(3, len(s) + 1):
            for index in range(len(s) - length + 1):
                if s[index] == s[index + length - 1] and dp[index + 1][length - 2]:
                    dp[index][length] = 1

        def dfs(index, seq):
            if index >= len(s):
                if index == len(s):
                    answers.append(seq[:])
                return
            else:
                for i in range(1, len(s) + 1 - index):
                    if dp[index][i]:
                        seq.append(s[index:index + i])
                        dfs(index + i, seq)
                        seq.pop()

        dfs(0, [])
        return answers

처음에 DFS 한 번으로 해결이 가능한가에 대해서 고민을 했고, 가능할 것 같았다.

문제는 그냥 DFS로 매번 회문을 체크하는 로직이 들어갈 때 TLE가 반드시 날 것 같았기 때문에 어떻게 해야 하나 고민을 했다.

 

결론적으로 우선 DP를 이용해 어떤 문자열에 대해서 n인덱스부터 length길이까지에 해당하는 문자열이 회문인지를 미리 구해놓은 뒤, DFS로 탐색을 하면서 조건에 맞는 경우만 계속 탐색을 하고 최종적으로 문자열을 전부 소모하는 index값이 len(s) 값 보다 크거나 같아지는 순간에 조건을 분기해 결과를 저장했다.

 

이전에 DP로 회문 판단 유무를 해결하는 문제를 풀어본 경험이 있어서 그것을 이용했다.

이 문제 정답률이 현재 53% 인데 정답률에 비해 굉장히 난이도가 높은 문제라고 생각한다.

 

추가

입력 문자열 길이 제한이 길지 않아서 그냥 DFS로 들어가도 통과가 되는 것 같다. 정답률이 5할이 넘는 이유가 있었다 ㅠㅠ