[LeetCode]Palindrome Partitioning

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

Palindrome Partitioning - LeetCode

 

문제 분석

주어진 문자열 s를 파티셔닝할 때 파티셔닝한 모든 문자열이 팰린드롬인 경우만 출력합니다.

 

처음 시도한 답안

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

        def dfs(i, path):
            if i == len(s):
                answer.append(path)
                return
            
            for j in range(i, len(s)):
                a = s[i:j+1]
                if a == a[::-1]:
                    dfs(j+1, path + [a])

        dfs(0, [])

        return answer

접근 방법

1. DFS를 활용해 풀이합니다.
2. dfs 내부에서
   1. 탐색한 깊이가 주어진 문자열 길이가 된다면 정답에 path를 추가합니다.
      주어진 문자열을 모두 사용했다는 의미입니다.
   2. 전달받은 i 부터 문자열 길이까지 반복합니다.
      1. 대상이 되는 문자열을 파티셔닝 합니다.
      2. 파티셔닝 된 문자열이 Palindrome 이라면 재귀적으로 dfs를 호출합니다.

DFS 내부의 순회가 동작하는 방식을 더 자세하게 설명하겠습니다.

1. 초기 상태에서
2. i=0, j=0, a[0:1]=a 인 상황, Palindrome O, path=[]
   1. i=1, j=1, a[1:1]=a 인 상황, Palindrome O, path=[a]
      1. i=2, j=2, a[2:3]=b 인 상황, Palindrome O, path=[a,a]
         1. i=3인 상황, 문자열의 길이와 동일, answer=[[a,a,b]]
   2. i=1, j=2, a[1:3]=ab 인 상황, Palindrome X, 재귀 호출 X
3. i=0, j=1, a[0:2]=aa 인 상황, Palindrome O, path=[]
   1. i=2, j=2, a[2:3]=b 인 상황, Palindrome O, path=[aa]
      1. i=3인 상황, 문자열의 길이와 동일, answer=[[a,a,b], [aa,b]]
4. i=0, j=2, a[0:3]=aab, Palindrome X, 재귀 호출 X

위와 같은 상황으로 재귀적인 호출이 수행됩니다.

 

문자열을 반복문을 통해 파티셔닝하고 재귀적으로 호출하는 것을 알아내기에 어려웠던 문제입니다.