Palindrome Partitioning
回文は、左から右に読んでも右から左に読んでも同じです。文字列 s を1つ以上の部分に分割し、各部分が回文になるようにして、そのすべての分割方法を返してください。
各分割は、順番に並べた部分を | でつないで表します。aab を a、a、b に分割すると、a|a|b になります。文字コードを比較して昇順に並べた分割を返してください。このとき、| はすべての小文字アルファベットの後に来ます。
関数
- sstring
- 切り取る小文字の文字列
- 戻り値string-array
- 各部分の間に | を入れて表した、s を回文に分割するすべての方法を昇順に並べたもの
制約
1 ≤ s.length ≤ 11sには小文字の英字のみが含まれています。- 同じ文字が11個並んだ文字列には1,024通りの分割があり、答えとしては最大です。
例
- 入力
- s = "aab"
- 出力
- ["aa|b", "a|a|b"]
- 説明
aa|bとa|a|bだけが、すべての部分が回文になっています。a|abはabが回文でないため失敗します。aa|bのほうが先に並びます。2文字目では、もう一方が|なのに対し、こちらはaであり、|はどの文字よりも後に並ぶためです。
- 入力
- s = "abba"
- 出力
- ["abba", "a|bb|a", "a|b|b|a"]
- 説明
abba自体が回文なので、切られていない文字列も分割の一つであり、最初に並びます。2文字目が文字だからです。a|bb|aはa|b|b|aより前に来ます。4文字目で、前者はb、後者は|だからです。
発展問題
長さが最大2,000の文字列について、sを回文に分割するための最小の切断回数を求められますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
1文字は常に回文なので、すべての文字列には少なくとも1つの分割方法があります。隣り合う文字の間の隙間を見てみましょう。分割とは、それぞれの隙間で、そこで区切るか区切らないかを選ぶことです。
左から右へ分割します。最初の部分は回文である接頭辞でなければなりません。それを選んだら、残りの文字列も同じ問題になります。
s[i..j]が回文かどうかを示す表を使えば、各判定を O(1) で行えます。次の部分が始まるインデックスで再帰し、その部分が回文となるすべての終了インデックスを試します。
|はすべての文字より後にソートされるため、最長の部分から試すと、分割結果はすでにソートされた順になります。
解説
文字間のn-1個の区切りをそれぞれ切るか切らないかで決めるため、分割方法は2^(n-1)通りあり、そのすべてが答えになり得ます。出力サイズをこれより小さくすることはできませんが、条件を満たさない分割は省けます。各分割を左から右へ構築し、回文の部分だけを切り出し、あらかじめ一度埋めた表から回文かどうかを読み取ります。
すべてのカットの組み合わせを試す
考え方
分割に 2^(n-1)-1 までの整数 0 を割り当て、各ビットで隙間を切るかどうかを表します。すべての部分文字列が回文である場合、その数の分割を残します。
最初の隙間に最上位ビットを割り当てると、数を小さい順に数えることで分割が辞書順に並びます。2つの数で異なる最上位ビットは、一方が切り、もう一方が切らない最も早い隙間を示します。その前では文字列は同じです。その隙間では、小さい数のほうには文字があり、大きい数のほうには | があり、これはすべての文字より後に並びます。aab の場合、1 は aa|b、3 は a|a|b を示します。
11文字の場合、これは11文字それぞれについての1,024個のマスクになります。無駄なのは、条件を満たさない分割です。abcdefghijk では、答えを1つ見つけるために1,024個すべてを作ります。
アルゴリズム
maskを 0 から2^(n-1)-1までループします。- 文字を順に見ていきます。最後のインデックスである場合、または
maskのビットn-2-iがセットされている場合は、文字iの後で区切ります。 - 各部分について、2つのポインターを内側に向かって動かして確認します。
- すべての部分が回文であれば、
|で部分を結合し、その文字列を答えに追加します。 - 答えを返します。最初の区切りが最上位ビットであるため、すでにソートされています。
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 を試し、その部分を追加して再帰し、取り除きます。1文字だけでも回文なので、すべての分岐は答えにたどり着きます。そのため、処理量は出力サイズに応じます。abcdefghijk の場合、探索は1つの経路をたどります。
s[start..end] が回文かどうかは多くの分岐で調べるため、表から読み取ります。s[i..j] は、s[i] == s[j] で、内側の s[i+1..j-1] も回文である場合、またはその部分の文字数が2文字以下の場合に、回文となります。
end を最後のインデックスから逆順に試すと、出力はソートされます。最初の部分が異なる2つの分割は、短い方の部分の末尾までは一致します。そこで短い方には | があり、長い方には文字があるため、最初の部分が長い方が先にソートされます。
アルゴリズム
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
回文分割の時間計算量はどれくらいですか？
同じ文字が並ぶ文字列では、2^(n-1) 通りの分割すべてが解となり、それぞれの長さは最大 2n-1 文字です: O(n × 2^n)。答えを書き出すだけでも同じコストがかかるため、これを上回る方法はありません。回文テーブルには時間と空間が O(n²) 追加で必要で、再帰には O(n) 必要です。
文字列は何通りに回文分割できますか？
最大で2^(n-1)通りです。これは、n-1個の隙間のそれぞれを切るかどうか選ぶ方法の数です。同じ文字が並ぶ文字列ではこの上限に達します。11文字なら1,024通りに分割できます。重複する文字のない文字列では分割はちょうど1通りで、各文字がそれぞれ単独になります。
回文分割は動的計画法ですか、それともバックトラッキングですか？
両方を使います。2^(n-1) 個までの分割を列挙するには、各分割を一つずつ構築する探索、つまりバックトラッキングを行います。動的計画法では、探索が参照する回文部分文字列の真偽値テーブルを、O(n²) で一度だけ埋めます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def partition(s):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
s = "aab"
期待される出力
["aa|b", "a|a|b"]