[1스4코2파] # 221. LeetCode 131. Palindrome Partitioning

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (221차)
[4코1파] 2023.01.13~ (213일차)
[1스4코1파] 2023.04.12~ (124일차)
[1스4코2파] 2023.05.03 ~ (102일차)

Today :

2023.08.13 [221일차]
backtracking
https://leetcode.com/problems/palindrome-partitioning/

LeetCode 131. Palindrome Partitioning

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

문제 설명

문자열 s가 주어 질때 해당 문자열을 파티셔닝하고, 이렇게 파티셔닝(나눈 하위 문자열이 palindrome 일 경우 하위 문자열을 retrun 함

• palindrome : 거꾸로 해도 본래의 문자 형태와 같은 것 (예: 토마토)

문제 풀이 방법

dfs로 푸는데, 여기서 주어진 s의 문자열의 길이만큼 돌면서, 해당 문자열의 인덱스만큼들의 부분 문자열인 substring들이 펠린드롬에 해당하는지 확인하는 메소드를 따로 만들어 줘서 그 조건에 부합하는 애들만 partition에 넣고 재귀로 돌아가면서 answer를 만들어야 함..

내 코드

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

        def dfs(i):
            if i>=len(s):
                ans.append(partition.copy())
                return 
            for j in range(i, len(s)):
                if self.isPalin(s, i, j):
                    partition.append(s[i:j+1])
                    dfs(j+1)
                    partition.pop()

        dfs(0)
        return ans

증빙

여담
dfs 문제의 축복이 끝이 없네..