a-077-palindrome-partitioning2026-08-03mediumleetcode #131neetcode150

팰린드롬 분할

#string#dynamic-programming#backtracking

↗ leetcode #131 · a-077-palindrome-partitioning

문제

· problem

P.a-077-palindrome-partitioning

팰린드롬 분할

↗ leetcode #131

문자열 s가 주어졌을 때, s를 분할하여 분할된 모든 부분 문자열이 팰린드롬이 되도록 하세요. s의 모든 가능한 팰린드롬 분할을 반환하세요.

제약

· 1 ≤ s.length ≤ 16
· s contains only lowercase English letters
· Every substring in the partition must be a non-empty palindrome

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

"aab"

[['a','a','b'],['aa','b']]

example 2input → output

"a"

[['a']]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
가능한 모든 분할을 반환해야 하나요, 아니면 하나의 유효한 분할만 반환해야 하나요?
☐
한 부분 문자열이 분할의 다른 위치에서 여러 번 사용될 수 있나요?
☐
분할의 부분 문자열들이 원본 문자열에서 연속된 순서로 나타나야 하나요?
☐
탐욕적 접근을 사용하여 항상 가장 긴 팰린드롬을 먼저 선택할 수 있나요?
☐
결과에서 중복된 분할을 제거해야 하나요?
☐
반환하기 전에 분할들을 정렬해야 하나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 결과 리스트 및 현재 분할 초기화

○

res, part = [], []

○

res = {}; part = {}

○

res = []; part = None

step 2· 기저 사례: 전체 문자열이 분할되었는지 확인│ 중첩

○

if i >= len(s):

○

if i > len(s):

○

if i == len(s) - 1:

step 3· 유효한 분할 기록│ │ 중첩

○

res.append(part.copy())

○

res.append(part)

○

res += [part]

step 4· 다음 분할 끝점의 모든 가능성 시도│ 중첩

○

for j in range(i, len(s)):

○

for j in range(i + 1, len(s)):

○

for j in range(0, len(s)):

step 5· 부분 문자열이 팰린드롬인지 확인│ │ 중첩

○

if self.isPali(s, i, j):

○

if s[i:j]:

○

if i < j:

step 6· 부분 문자열을 분할에 추가하고 계속 탐색│ │ │ 중첩

○

part.append(s[i : j + 1])

○

part.append(s[i : j])

○

part.append(s[i : j + 1]); dfs(j)

step 7· 마지막 추가한 부분 문자열 제거로 백트래킹│ │ │ 중첩

○

part.pop()

○

part.clear()

○

part = part[:-1]

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def partition(self, s: str) -> List[List[str]]:

        res, part = [], []

        def dfs(i):

            if i >= len(s):

                res.append(part.copy())

                return

            for j in range(i, len(s)):

                if self.isPali(s, i, j):

                    part.append(s[i : j + 1])

                    dfs(j + 1)

                    part.pop()

        dfs(0)

        return res

    def isPali(self, s, l, r):

        while l < r:

            if s[l] != s[r]:

                return False

            l, r = l + 1, r - 1

        return True

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

"aab"

→

[['a','a','b'],['aa','b']]

case 2

"a"

→

[['a']]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.