Word Break
文字列 s と単語のリスト wordDict が与えられます。s を wordDict の単語だけからなる部分に分割できる場合は true を、そうでない場合は false を返してください。
分割した部分は元の順序を保ち、すべて合わせると s の各文字をちょうど1回ずつ使います。単語は何度でも使えますが、すべての単語を使う必要はありません。
関数
- sstring
- 単語に分割する文字列
- wordDictstring-array
- 使用できる単語（それぞれ何度でも使用できます）
- 戻り値boolean
- true は、s を辞書にある単語に分割できる場合、false はそれ以外の場合
制約
1 ≤ s.length ≤ 3001 ≤ wordDict.length ≤ 10001 ≤ wordDict[i].length ≤ 20sとすべての単語は、小文字の英字のみで構成されています。-
wordDict内の単語はすべて異なります。
例
- 入力
- s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
- 出力
- true
- 説明
sun、flower、seedのように分割します。sunの後にflowを取るとerが残りますが、erで始まる単語はないため、最初に当てはまる単語が必ずしも正しいとは限りません。
- 入力
- s = "bananaban"wordDict = ["ban", "ana"]
- 出力
- true
- 説明
ban+ana+banは文字列全体をカバーし、banを2回使用していますが、これは許可されています。
- 入力
- s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
- 出力
- false
- 説明
pine+appleもpineappleもtartを残します。そこに当てはまるのはtarだけで、最後にtが1文字だけ残るため、どの分割もうまくいきません。
発展問題
有効な分割で使用できる最少の単語数を返します。分割できない場合は -1 を返します。表では何が変わり、実行時間は変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どの分割でも、最初の部分は
sで始まる単語です。それを選んだら、残る疑問は何でしょうか？あるインデックスから末尾までの文字を切り取れるかどうかは、そのインデックスだけで決まります。そのような問いは
n + 1個しかないので、それぞれの答えを記憶しておきましょう。特にfalseの答えはすべて記憶してください。canEnd[i]は、最初のi文字を分割できるかどうかを表し、canEnd[0] = trueとします。このとき、あるcanEnd[start]がtrueで、startからendまでの文字が単語を構成する場合、canEnd[end]はtrueになります。単語はハッシュセットに格納し、最長の単語より長くない部分だけを試します。
解説
一度に1語ずつ確定していく方法ではうまくいかず、あらゆる区切り方を試す方法は指数関数的になります。しかし、sの残りの部分を区切れるかどうかは、開始位置だけで決まるため、考えるべき問いはn + 1個だけです。以下では、nはsの長さ、mは単語数、Lは最長の単語の長さです。
すべての位置ですべての単語を試す
正しいが、最大のテストでは終わらない
考え方
最初の部分は、sが始まる文字で始まる単語でなければなりません。そのような単語をそれぞれ試し、残った文字について同じ問いを繰り返します。残りが空なら、すべての文字を切り分けたことになります。最初の単語をすべて試し、次に2番目の単語をすべて試せば、有効な切り分けを見落とすことはありません。
同じ残りを何度も調べています。aが299個続き、その後にbが1個あり、単語がa、aaからaが10個のものまである場合、aをブロックに分けてbまで到達して失敗する方法は10^89通りを超え、再帰はそれらをすべて試します。
アルゴリズム
canSplit(start)を記述します。startから末尾までの文字を分割できるでしょうか？startがsの長さと等しい場合は、trueを返します。sがインデックスstartで含む各単語について、canSplit(start + its length)がtrueなら、trueを返します。- それ以外の場合は
falseを返します。答えはcanSplit(0)です。
def wordBreak(s, wordDict):
def can_split(start):
# Can s[start:] be cut into dictionary words?
if start == len(s):
return True # nothing left to cut
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
return True
return False
return can_split(0)メモ化を使った再帰
考え方
余りの答えはstartのみに依存し、n + 1個の値を取ります。aの例では、インデックス20の余りには、10個ずつのブロックを2つ使った後、aを1つずつ20回使った後、そしてほかにも無数の方法で到達しますが、どの場合もfalseです。各startの答えを一度だけ保存し、再利用します。
メモにはfalseの答えも保持する必要があります。trueが見つかると探索全体がただちに終了するため、繰り返される処理は失敗する分岐で発生します。
各startではすべての単語を試し、最大L文字を比較します。時間計算量はO(n × m × L)で、文字の比較は最大6 × 10^6回、空間計算量はO(n)です。
アルゴリズム
- インデックスごとに1つの枠を用意し、それぞれに未計算の印を付けたメモを作ります。
canSplit(start)では、sの末尾に達したらtrueを返し、枠に答えが保存されていればその答えを返します。- それ以外の場合は、単純な再帰と同様にすべての単語を試し、結果を枠に保存してから（
falseも含めて）返します。
def wordBreak(s, wordDict):
memo = [None] * len(s) # memo[start]: answer for s[start:], None until worked out
def can_split(start):
if start == len(s):
return True
if memo[start] is not None:
return memo[start]
result = False
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
result = True
break
memo[start] = result
return result
return can_split(0)ハッシュセットを使って接頭辞をボトムアップで処理する
考え方
接頭辞について考えます。canEnd[i] は、先頭の i 文字を分割できるかどうかを表します。空の接頭辞には単語が必要ないため、canEnd[0] は true です。先頭の end 文字を分割できるのは、最後の部分、つまり start から end までが単語であり、かつ canEnd[start] が true の場合に限ります。左から右へ埋めていけば、必要な canEnd[start] はすでに分かっています。
単語はハッシュセットに入れます。単語の長さは最大でも L なので、辞書がどれだけ大きくても、end で終わる L 個の部分だけが一致する可能性があります。sunflowerseed では、canEnd が 0、3、7、9、13 で true になります。7 で行き止まりになっても問題ありません。
n 個の位置それぞれで最大 L 個の部分を検索し、それぞれの作成とハッシュ計算に最大 L ステップかかります。つまり O(n × L²) で、最大でも 1.2 × 10^5 ステップです。これにセット用の O(m × L) が加わります。
アルゴリズム
- 単語をハッシュセットに入れ、最長の長さ
Lを確認します。 n + 1個の要素を持つcanEndを作成し、すべてをfalseにして、canEnd[0]をtrueに設定します。endを 1 からnまで、lengthを 1 からmin(L, end)までそれぞれ繰り返します。canEnd[end-length]がtrueで、かつendで終わるその長さの部分文字列がセットに含まれている場合、canEnd[end]をtrueに設定して終了します。canEnd[n]を返します。
def wordBreak(s, wordDict):
words = set(wordDict)
longest = max(len(word) for word in wordDict)
n = len(s)
# can_end[i]: the first i letters split into dictionary words
can_end = [False] * (n + 1)
can_end[0] = True # the empty prefix needs no words
for end in range(1, n + 1):
# The last word is s[end-length:end], and no word is longer than longest.
for length in range(1, min(longest, end) + 1):
if can_end[end - length] and s[end - length:end] in words:
can_end[end] = True
break
return can_end[n]
落とし穴と境界ケース
- 貪欲に切り分ける。最長のものから先に切ると、
carpetalはcarpetとして切られ、alが残ってしまいます。しかし、car+petalならうまくいきます。最短のものから先に切ると、sunflowerseedで行き詰まります。 - メモに
trueの結果だけを保存する。繰り返しの処理はfalseの分岐で発生するため、a の例は指数時間のままです。 - テーブルの要素数を1つ少なくする。
canEndには、接頭辞の長さ0からnまでに対応するn + 1個の要素が必要です。 sの末尾を越えて比較する。たとえば、残りがabなのに単語abcと比較する場合です。まず長さを確認してください。- Lua と R では、文字列の位置は1から始まります。文字
eで終わる長さkの部分文字列は、e-k+1から始まります。
よくある質問3
Word Break の時間計算量はどれくらいですか？
ハッシュセットを使ったボトムアップの表は O(m × L + n × L²) で実行されます。ここで、n は s の長さ、m は単語数、L は最長の単語です。各位置ですべての単語を比較すると、O(n × m × L) のコストがかかります。単純な再帰は指数時間になります。
Word Breakは動的計画法の問題ですか、それともグラフの問題ですか？
両方です。動的計画法としては、canEnd[i]は最初のi文字を分割できるかどうかを示します。グラフとして見ると、各インデックスがノードで、間の文字が単語を形成するときにiからjへの辺があります。そして、0からnに到達できるかを調べます。幅優先探索でも、表を使う場合と同じ処理ができます。
True または false を返す代わりに、すべての文を一覧表示するにはどうすればよいですか？
バックトラックでは、各インデックスで当てはまる単語をすべて試し、残りの部分で再帰し、各インデックスの文のリストを記憶します。まず真偽値テーブルを実行し、分割できない文字列は探索をスキップします。文の数は指数関数的に増える可能性があるため、出力サイズが実行時間を決定します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def wordBreak(s, wordDict):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "sunflowerseed" wordDict = ["sun", "flow", "flower", "seed"]
期待される出力
true