単語分割可能か (Word Break)

左から欲張って切ると、行き止まる

catsandog という文字列と、cats、cat、sand、and、dog という辞書が渡されます。辞書の単語だけをつなげて、この文字列を作れるでしょうか。

左から順に、辞書にある一番長い単語で切っていきます。cats が取れました。残りは andog。and が取れました。残りは og で、辞書にありません。行き止まりです。

では cat で切っていたら。残りは sandog で、sand が取れて、残りはやはり og。こちらも行き止まりです。この文字列は作れません。

大事なのは、1 回目の切り方を変えると 2 回目以降の選択肢が丸ごと変わるという点です。辞書に単語があるかどうかは一瞬で調べられます。難しいのは どこで区切るか の分かれ道のほうです。

分かれ道は、印に置き換える

分かれ道を素直にたどると、切るたびに枝分かれして指数的に増えます。しかも別々の枝の先で「残りの og から作れるか」という同じ問いを何度も解き直します。編集距離のときと同じ無駄です。

そこで、枝をたどるのをやめて、左から順に印を立てていきます。印の意味は「先頭からここまでは、辞書の単語だけで作れる」です。

ある位置に印が立つのは、その手前のどこかに印が立っていて、そこから今の位置までの文字列が辞書にあるとき です。手前の印は 1 つ見つかれば十分なので、見つけた時点で次の位置へ進めます。

今の位置からどこまで進めるかを見るのは、この形です。

cat と cats の 2 つが出てきます。これが分かれ道です。印を立てる方式なら、どちらの行き先にも印を立てておけばよく、その先はどちらの道からたどっても 1 度しか調べません。枝の数ではなく、文字の位置の数だけ働けば済みます。

辞書は必ず集合 (set や Set) に入れ替えてから使ってください。配列のまま in や includes で調べると、位置を 1 つ試すたびに単語の数だけなぞることになり、全体の速さが一段落ちます。

出発点の印を忘れない

一番左、まだ 1 文字も見ていない位置にも印が要ります。「空の文字列は、単語を 0 個つなげて作れている」とみなすためです。ここに印が立っていないと、手前の印が 1 つも見つからず、どこにも印が立たないまま必ず偽になります。

最後に見るのは、文字列の長さと同じ位置の印です。印の入れ物は文字数より 1 つ長くなるので、うっかり 1 つ手前を見ると、最後の 1 文字を無視した答えになります。

やってみよう

• leetcode と ["leet", "code"] で真になることを確かめる
• applepenapple と ["apple", "pen"] は真。同じ単語を何度使ってもよい
• aaaaaaa と ["aaaa", "aaa"] を手で追う。どこに印が立つか、左から順に書き出してみる

1. 戻り値は分割可能か否か (boolean)
2. 辞書を set / HashSet / map に変換してから判定すること (in 判定 O(1))
3. dp[i] = s の最初 i 文字が分割可能か、として DP で求めること