Palindrome Partitioning II
あらかじめ計算した回文テーブルと1次元DPを組み合わせ、文字列を回文に分割するために必要な最小カット数を求めます。
「Palindrome Partitioning II」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
問題: 分割に必要な最小カット数
回文分割 IIでは、文字列 s が与えられたとき、分割後のすべての部分文字列が回文になるようにするためのカット数の最小値を求めます。'aab' の場合、['aa', 'b'] と1回カットすればよいので、答えは1です。'a' の場合は、すでに回文なので答えは0です。この問題では、2つのDPフェーズを組み合わせます。まず、どの部分文字列が回文かを事前計算し、次に1D DPを使って最小カット数を求めます。
フェーズ1: 回文テーブルの事前計算
まず、区間DPを使って、s[i..j] が回文なら is_pal[i][j] = True となるように設定します。計算量は O(n²) 時間、O(n²) 空間です。別の方法として、中心からの展開で同じテーブルを O(n²) 時間で埋めることもできます。このテーブルが必要なのは、1DカットDPの中で is_pal[i][j] を何度も参照するためです。事前計算しておけば、カットDPのループ内で回文判定を繰り返さずに済みます。
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))フェーズ2: 1DカットDPの準備
cuts[i] を、s[0..i] を分割するための最小カット数と定義します。s[0..i] 自体が回文なら、cuts[i] = 0 です。それ以外の場合は、すべての分割位置を試します。j を 0 から i-1 まで動かし、s[j+1..i] が回文なら、cuts[i] = min(cuts[i], cuts[j] + 1) とします。これは、最後の分割部分が s[j+1..i] だとしたらどうなるかを考えています。その場合、先頭部分には cuts[j] 回のカットが必要で、さらに1回カットすることになります。
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]完全な解法とトレース
'aab' を例に追ってみましょう。回文テーブルは、is_pal[0][0]='a'=T、is_pal[1][1]='a'=T、is_pal[2][2]='b'=T、is_pal[0][1]='aa'=T、is_pal[1][2]='ab'=F、is_pal[0][2]='aab'=F です。カット数は、cuts[0]=0（'a' は回文）、cuts[1]=0（'aa' は回文）となります。cuts[2] では、'aab' は回文ではないため、j=1 を試します。is_pal[2][2]=T なので、cuts[2] = cuts[1]+1 = 1 です。答えは1です。
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))時間計算量と空間計算量
フェーズ1（回文テーブル）は、O(n²) 時間・O(n²) 空間で実行されます。フェーズ2（カットDP）では、n 個の位置を走査する外側のループと、n 個の分割位置を走査する内側のループがあるため、こちらもO(n²) 時間です。全体では、O(n²) 時間・O(n²) 空間となります。カット配列に必要な空間は O(n) まで削減できますが、回文テーブルには依然として O(n²) が必要です。面接では O(n²) が期待されます。Manacher's を使う O(n) 解法は、通常の出題範囲を超えています。
回文テーブルへの中心からの展開の適用
回文テーブルに区間DPを使う代わりに、中心からの展開で is_pal を埋めることもできます。各中心位置から外側へ展開し、見つかったすべての回文を記録します。これも O(n²) 時間・O(n²) 空間ですが、キャッシュの局所性がよいため、実際にはより高速になる場合があります。どちらの方法も、面接では有効です。
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')すべての分割を列挙する（パートI）
回文分割 I（関連問題）では、すべての部分文字列が回文になるすべての有効な分割を列挙します。事前計算した回文テーブルを枝刈りの判定に使い、バックトラッキングで解きます。最小カットDPが解の個数を数えるのに対し、こちらは指数関数的に多くなり得る解を列挙するため、まったく異なるアプローチが必要です。
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]cuts を n-1 で初期化
よく使われる工夫として、inf ではなく cuts[i] = i で初期化します。s[0..i] の最悪ケースは各文字を1つずつ分割することであり、その場合のカット数は i になるためです。これにより、コード内で inf を確認する必要がなくなります。is_pal[0][i] が true の場合は、値を0に上書きします。この初期化によってカット数の上限が明確になり、コードも少し簡潔になります。
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]別解: 個別のテーブルを使わない1パスDP
洗練された別解として、回文テーブルとカットDPを同時に埋める方法があります。各中心から回文を展開しながら、すぐに cuts 配列を更新します。回文 s[l..r] に対して、cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)) と更新できます。これにより、O(n²) のテーブル走査を別途行わずに済むため、時間制限のある面接中にも実装しやすい場合があります。
考慮すべきエッジケース
回文分割 II で重要なエッジケースは次のとおりです。(1) 1文字の文字列はカット数0を返します。(2) すでに回文になっている文字列はカット数0です。(3) すべての文字が異なる文字列では、n-1 回のカットが必要です。(4) すべて同じ文字の文字列（例: 'aaaa'）では、文字列全体が回文なのでカット数は0です。is_pal[0][i] = True による早期終了を、解法が正しく処理できることを必ず確認してください。
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2面接での説明のコツ
面接でこの問題を説明するときは、2段階のアプローチから始めてください。まず回文テーブルを作り、次にカット配列に対して1D DPを実行します。コーディングの前に、漸化式を言葉で説明してください。回文テーブルには O(n²) 個のエントリがあり、それぞれを区間DPの漸化式を使って O(1) で埋められることにも触れましょう。正しさを落ち着いて示すため、完全な解法を書く前に、必ず例を使って処理を追ってください。
クイックチェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、回文分割 II では、回文テーブルを事前計算してから1DカットDPを実行するという2段階のDPを使うこと、カットの漸化式は、s[j..i] が回文となるすべての j に対して cuts[i] = min(cuts[j-1] + 1) となること、そして全体の計算量は O(n²) 時間・O(n²) 空間であることを学びました。次は、巧妙な逆向きの区間DPアプローチを使うバルーン破裂問題に取り組みます。
よくある質問
「Palindrome Partitioning II」レッスンは無料ですか？
はい。「Palindrome Partitioning II」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「Palindrome Partitioning II」で何を学びますか？
あらかじめ計算した回文テーブルと1次元DPを組み合わせ、文字列を回文に分割するために必要な最小カット数を求めます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「Palindrome Partitioning II」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 区間DPのパターンと埋める順序
- 最長回文部分列と部分文字列
- Palindrome Partitioning II
- Burst Balloons：逆向き区間DP