Palindrome Partitioning

Q: Palindrome Partitioning의 시간 복잡도는 얼마인가요?

같은 문자로 이루어진 문자열에서는 2^(n-1) 개의 모든 분할이 정답이며, 각 정답의 길이는 최대 2n-1 자입니다: O(n × 2^n) . 정답을 출력하는 데에도 그만큼의 비용이 들기 때문에, 이를 능가하는 방법은 없습니다. 팰린드롬 표에는 O(n²) 의 시간과 공간이 필요하고, 재귀에는 O(n) 이 필요합니다.

Q: 문자열은 몇 개의 회문 분할을 가질 수 있나요?

최대 2^(n-1) 개이며, n-1 개의 간격 중 어느 곳을 자를지 선택하는 각 방법마다 하나씩입니다. 같은 문자로 이루어진 문자열은 그 상한에 도달합니다. 11개의 문자라면 1,024가지로 나뉩니다. 반복되는 문자가 없는 문자열은 정확히 한 가지로 나뉘며, 각 문자가 하나씩 따로 놓입니다.

Q: Palindrome Partitioning은 동적 프로그래밍인가요, 아니면 백트래킹인가요?

둘 다 사용합니다. 2^(n-1) 개까지의 분할을 나열하려면 각 분할을 조각별로 만들어 가는 탐색, 즉 백트래킹이 필요합니다. 동적 프로그래밍은 탐색에서 읽어 들이는 회문 부분 문자열의 참 또는 거짓을 나타내는 표를 제공하며, 이 표는 O(n²) 에 한 번 채워집니다.

보통백트래킹 동적 계획법

+10

회문은 왼쪽에서 오른쪽으로 읽어도, 오른쪽에서 왼쪽으로 읽어도 똑같이 읽힙니다. 문자열 s를 하나 이상의 조각으로 나누어 모든 조각이 회문이 되도록 하고, 가능한 모든 방법을 반환하세요.

각 분할은 조각을 순서대로 |로 이어서 나타내세요. 예를 들어 aab를 a, a, b로 나누면 a|a|b가 됩니다. 문자 코드를 비교해 오름차순으로 정렬한 분할을 반환하세요. 따라서 |는 모든 소문자 뒤에 옵니다.

함수

partition(s: string) → string-array

sstring: 잘라낼 소문자 문자열
반환값string-array: s를 회문으로 나눈 모든 경우를 조각 사이에 |를 넣어 오름차순으로

제약 조건

1 ≤ s.length ≤ 11
s에는 소문자 영어 문자만 포함되어 있습니다.
같은 글자 11개로 이루어진 문자열은 1,024가지로 분할할 수 있어 답이 가장 큽니다.

예제

입력: s = "aab"
출력: ["aa|b", "a|a|b"]
설명: aa|b와 a|a|b만 모든 조각이 회문입니다. a|ab는 ab에서 조건을 만족하지 못합니다. aa|b가 사전순으로 먼저 옵니다. 두 번째 문자에서 한쪽은 a이고 다른 쪽은 모든 문자보다 뒤에 오는 |이기 때문입니다.

입력: s = "abba"
출력: ["abba", "a|bb|a", "a|b|b|a"]
설명: abba 자체가 회문이므로, 자르지 않은 문자열은 분할 결과이며 먼저 정렬됩니다. 두 번째 문자가 문자입니다. a|bb|a는 a|b|b|a보다 앞에 옵니다. 네 번째 문자에서 전자는 b이고 후자는 |이기 때문입니다.

후속 질문

길이가 최대 2,000인 문자열에 대해 s를 회문으로 나누는 최소 자르기 횟수를 찾을 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

문자 사이의 n-1개 간격은 각각 자르거나 자르지 않으므로 2^(n-1)개의 분할이 있으며, 이 모든 분할이 정답이 될 수 있습니다. 출력 크기보다 더 나은 방법은 없지만, 실패하는 분할은 건너뛸 수 있습니다. 각 분할을 왼쪽에서 오른쪽으로 만들고, 회문인 부분만 잘라 내며, 한 번 채워 둔 테이블에서 회문 여부를 확인하세요.

모든 절단 집합을 시도해 보세요

핵심 아이디어

분할에 0부터 2^(n-1)-1까지의 정수를 매기고, 각 비트는 하나의 간격이 잘리는지를 나타냅니다. 모든 조각이 회문이면 해당 숫자의 분할을 유지합니다.

첫 번째 간격에 가장 높은 비트를 할당하면, 숫자를 오름차순으로 세는 순서가 분할의 오름차순 목록이 됩니다. 두 숫자에서 서로 다른 가장 높은 비트는 한쪽은 자르고 다른 쪽은 자르지 않는 가장 이른 간격입니다. 그 앞에서는 문자열이 같고, 그 위치에서 더 작은 숫자에는 문자가, 더 큰 숫자에는 모든 문자보다 뒤에 정렬되는 |가 있습니다. aab의 경우, 1은 aa|b를, 3은 a|a|b를 나타냅니다.

문자 11개에서는 문자 11개로 이루어진 마스크가 1,024개입니다. 낭비되는 부분은 거부되는 분할에 있습니다. abcdefghijk는 답 하나를 찾기 위해 1,024개를 모두 만듭니다.

알고리즘

mask를 0부터 2^(n-1)-1까지 반복합니다.
문자들을 순회합니다. i가 마지막 인덱스이거나 mask의 n-2-i 비트가 설정되어 있으면 문자 i 뒤에서 조각을 끝냅니다.
각 조각을 양쪽에서 안쪽으로 이동하는 두 포인터로 확인합니다.
모든 조각이 회문이면 조각들을 |로 연결하고 문자열을 답에 추가합니다.
답을 반환합니다. 첫 번째 간격이 가장 높은 비트이므로 답은 이미 정렬되어 있습니다.

def partition(s):
    n = len(s)
    result = []
    # Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
    # masks up from 0 lists the splits in sorted order.
    for mask in range(1 << (n - 1)):
        pieces = []
        start = 0
        for i in range(n):
            if i == n - 1 or (mask >> (n - 2 - i)) & 1:
                pieces.append(s[start:i + 1])
                start = i + 1
        if all(piece == piece[::-1] for piece in pieces):
            result.append("|".join(pieces))
    return result

회문 테이블을 사용한 백트래킹

핵심 아이디어

첫 번째 조각은 회문 접두사 s[0..end]이고, 나머지를 나누는 것은 end+1부터 시작하는 같은 문제입니다. 따라서 backtrack(start)는 s[start..end]가 회문인 모든 end를 시도하고, 해당 조각을 추가한 뒤 재귀 호출하고, 조각을 제거합니다. 한 글자도 회문이므로 모든 분기는 답으로 끝납니다. 따라서 작업량은 출력 크기에 비례합니다. abcdefghijk의 경우 탐색은 한 경로를 따라갑니다.

s[start..end]가 회문인지 여부는 여러 분기에서 확인하므로, 테이블에서 읽어 옵니다. s[i..j]는 s[i] == s[j]이고 내부의 s[i+1..j-1]가 1이거나 조각의 글자 수가 2 이하일 때 1입니다.

end를 마지막 인덱스부터 내림차순으로 시도하면 정렬된 출력이 나옵니다. 첫 번째 조각이 다른 두 분할은 더 짧은 조각이 끝나는 지점까지 일치합니다. 그 지점에서 더 짧은 조각에는 |가 있고 더 긴 조각에는 글자가 있으므로, 첫 번째 조각이 더 긴 쪽이 먼저 정렬됩니다.

알고리즘

n-1부터 0까지 i를 순회하며 pal[i][j]를 채웁니다. 조건은 s[i] == s[j]이고, j-i < 2이거나 pal[i+1][j-1]인 것입니다.
backtrack(start)를 작성합니다. start가 n과 같으면 현재 조각들을 |로 연결하고 문자열을 저장합니다.
그렇지 않으면 end를 n-1부터 start까지 순회하고, pal[start][end]가 아니면 건너뜁니다.
s[start..end]를 조각들에 추가하고 backtrack(end+1)을 호출한 다음, 해당 조각을 제거합니다.
backtrack(0)을 호출하고 이미 정렬된 분할 결과를 반환합니다.

def partition(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways.
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    result = []
    parts = []

    def backtrack(start):
        if start == n:
            result.append("|".join(parts))
            return
        # Longest piece first: "|" sorts after every letter, so a longer
        # first piece gives a smaller string and the output stays sorted.
        for end in range(n - 1, start - 1, -1):
            if pal[start][end]:
                parts.append(s[start:end + 1])
                backtrack(end + 1)
                parts.pop()

    backtrack(0)
    return result

함정과 경계 사례

가장 짧은 조각부터 시도하는 것. 분할은 맞지만 순서가 잘못되었습니다. aa|b보다 a|a|b가 먼저 나옵니다.
언어 또는 로캘 규칙을 따르는 비교를 사용해 마지막에 정렬하는 것. 이 경우 |가 문자보다 앞에 올 수 있습니다. 문자 코드를 비교하거나 분할을 순서대로 생성하세요.
i를 증가시키면서 회문 테이블을 채우는 것. 그러면 pal[i+1][j-1]을 계산하기 전에 읽게 됩니다. i를 n-1부터 내림차순으로 채우세요.
포함되는 end와 끝 인덱스를 제외하는 부분 문자열을 혼용하는 것. 조각 s[start..end]에는 end-start+1개의 문자가 있습니다.
결합된 문자열 대신 조각이 담긴 공유 목록을 저장하는 것. 탐색 과정에서 해당 목록이 계속 바뀌므로 저장된 모든 항목이 결국 같아집니다.

자주 묻는 질문3

Palindrome Partitioning의 시간 복잡도는 얼마인가요?

같은 문자로 이루어진 문자열에서는 2^(n-1)개의 모든 분할이 정답이며, 각 정답의 길이는 최대 2n-1자입니다: O(n × 2^n). 정답을 출력하는 데에도 그만큼의 비용이 들기 때문에, 이를 능가하는 방법은 없습니다. 팰린드롬 표에는 O(n²)의 시간과 공간이 필요하고, 재귀에는 O(n)이 필요합니다.

문자열은 몇 개의 회문 분할을 가질 수 있나요?

최대 2^(n-1)개이며, n-1개의 간격 중 어느 곳을 자를지 선택하는 각 방법마다 하나씩입니다. 같은 문자로 이루어진 문자열은 그 상한에 도달합니다. 11개의 문자라면 1,024가지로 나뉩니다. 반복되는 문자가 없는 문자열은 정확히 한 가지로 나뉘며, 각 문자가 하나씩 따로 놓입니다.

Palindrome Partitioning은 동적 프로그래밍인가요, 아니면 백트래킹인가요?

둘 다 사용합니다. 2^(n-1)개까지의 분할을 나열하려면 각 분할을 조각별로 만들어 가는 탐색, 즉 백트래킹이 필요합니다. 동적 프로그래밍은 탐색에서 읽어 들이는 회문 부분 문자열의 참 또는 거짓을 나타내는 표를 제공하며, 이 표는 O(n²)에 한 번 채워집니다.

def partition(s):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자

s = "aab"

예상 출력

["aa|b", "a|a|b"]