Word Break

Q: Word Break の時間計算量はどれくらいですか？

ハッシュセットを使ったボトムアップのテーブルは、 O(m × L + n × L²) 時間で実行されます。ここで、 n は s の長さ、 m は単語数、 L は最長の単語の長さです。セットの構築では各単語を1回ずつ読み込み、 n 個の位置それぞれで、長さが最大 L 文字の部分文字列を最大 L 個検索します。代わりに各位置ですべての単語を比較すると、計算量は O(n × m × L) です。メモ化なしの単純な再帰は指数時間になります。

Q: Word Break で貪欲法が失敗するのはなぜですか？

貪欲なルールは1つの単語を選ぶと、決して選び直しません。最長優先では carpetal を carpet と al に分割しますが、 car + petal ならうまくいきます。最短優先では sunflowerseed を sun + flow に分割し、 erseed で行き詰まります。動的計画法は、分割によって到達できるすべての位置を保持するため、正しい位置を見失うことがありません。

Q: Word Breakは動的計画法の問題ですか、それともグラフの問題ですか？

どちらの見方でも機能します。動的計画法としては、 canEnd[i] は最初の i 文字を分割できるかどうかを答え、小さな接頭辞から構築されます。グラフとしては、各インデックスがノードで、 i から j までの文字が単語を形成するときに i から j への辺があります。そして、ノード0からノード n に到達できるかどうかを調べます。訪問済み集合を使った幅優先探索でも、表と同じ処理ができます。

ふつう動的計画法ハッシュ

+10

文字列 s と単語のリスト wordDict が与えられます。s を分割して、すべての部分が wordDict に含まれる単語になる場合は true を返し、そうでない場合は false を返してください。

分割した部分は元の順序を保ち、合わせると s のすべての文字をちょうど1回ずつ使います。同じ単語は何度でも使用でき、すべての単語を使う必要はありません。

関数

wordBreak(s: string, wordDict: string-array) → boolean

sstring: 単語に分割する文字列
wordDictstring-array: 好きなだけ何度でも使える単語
戻り値boolean: s を辞書にある単語に分割できる場合は true、そうでない場合は false

制約

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
sとすべての単語には小文字の英字のみが含まれています。
wordDict 内の単語はすべて異なります。

例

入力: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
出力: true
説明: sun、flower、seedのように分割します。sunの後にflowを続けても、残った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なので、どの分割もうまくいきません。

提出時に隠しテスト+21件

発展問題

有効な分割で使用できる単語数の最小値を返します。sを分割できない場合は-1を返します。表の何が変わり、実行時間は変わりますか？

ヒント

1つずつ開いてください。開くたびに少しずつ答えに近づきます。

3個中0個を表示

解説

貪欲に分割すると、どちらの方向でもうまくいきません。最短の単語を先に取るとsunflowerseedはsun + flowに分割され、最長の単語を先に取るとcarpetalはcarpetに分割され、alが残ってしまいます。そこで、選択肢を試す必要があります。文字列は指数関数的に多くの方法で分割できる可能性があります。この問題を解決する鍵は、文字列の残りを分割できるかどうかは、残りの文字列がどこから始まるかだけで決まる点です。つまり、異なる問いはn + 1個しかありません。以下では、nはsの長さ、mは単語の数、Lは最長の単語の長さです。

すべての単語をすべての位置で試す

正しいが、最大のテストでは終わらない

考え方

sを左から読みます。最初の部分は、sが先頭に持つ単語でなければなりません。そのような単語を一つずつ試し、残りの文字について同じ問いを考えます。最後まで切り分けられる単語が一つでもあれば、答えはtrueです。なければ、falseです。何も残っていなければ、すべての文字を切り分けたことになるので、成功とみなします。

これは、最初の単語として可能なものをすべて試し、次に2番目の単語として可能なものをすべて試す、というように進むため、有効な切り分けを見落とすことはありません。また、返されるtrueには必ず実際の切り分けが伴います。

同じ残りの部分を何度も調べるため、処理は遅くなります。aを299個並べ、その後にbを1つ置き、単語としてa、aa、というようにaが10個のものまで使える場合を考えてみましょう。aを最大10個ずつのブロックに切り分ける方法はどれもbまでたどり着いてそこで失敗し、そのような方法は10^89通りを超えます。再帰処理はfalseと答える前に、そのすべてを試さなければなりません。

アルゴリズム

start インデックスから末尾までの文字を単語に分割できるかどうかを判定するヘルパー canSplit(start) を書きます。
start が s の長さと等しい場合は、true を返します。
各単語について、start インデックスから始まる位置に s がその単語を含んでいるかを確認します。
含んでいて、canSplit(start + length of the word) が 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 を 20 個使った後、そしてほかにも非常に多くの方法で到達できますが、その答えは毎回 false です。各開始位置の答えを最初に計算したときに保存し、その後は読み戻します。

メモのスロットには 3 つの状態が必要です。まだ計算されていない状態、true、false です。重要なのは false の答えです。true が見つかると探索全体がただちに終了するため、通常の再帰で繰り返される処理は、すべて失敗する分岐で行われます。

各開始位置は一度だけ計算され、すべての単語を試し、それぞれ最大 L 文字を比較するため、時間計算量は O(n × m × L) です。ここでは文字のチェックは最大で 300 × 1000 × 20 = 6 × 10^6 回です。メモと呼び出しスタックに必要な空間は O(n) で、呼び出しは最大 300 段まで入れ子になります。

アルゴリズム

インデックスごとに1つのスロットを持つメモを作り、それぞれに未計算の印を付けます。
canSplit(start)では、文字列の末尾でtrueを返し、startのスロットに値が格納されている場合は、その答えを返します。
それ以外の場合は、単純な再帰と同様に、startから始まるすべての単語を試し、残りの部分を分割できる最初の単語が見つかったらそこで停止します。
falseも含め、結果をスロットに格納して返します。
canSplit(0)を返します。

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] はすべてすでに分かっています。

各位置で m 個すべての単語と比較する代わりに、単語をハッシュセットに入れ、最後の部分としてあり得る文字列を検索します。どの単語も長さは L 以下なので、end で終わる L 個の部分文字列だけが一致する可能性があります。sunflowerseed では、canEnd は 0、3（sun）、7（flow）、9（flower）、13（位置 9 の後の seed）で true になるため、答えは true です。位置 7 から先には進めません。er で始まる単語はなく、表はそのことを気にしません。

n 個の位置それぞれで最大 L 個の部分文字列を検索し、部分文字列の構築とハッシュ化には最大 L ステップかかります。したがって、これは O(n × L²) であり、辞書の大きさにかかわらず、最大で 300 × 20 × 20 = 1.2 × 10^5 文字分のステップです。セットの構築では各単語を 1 回読み込むため、O(m × L) です。よって全体では O(m × L + n × L²) となります。セットは O(m × L) 個の文字に相当する単語を保持し、表には n + 1 個のフラグが入ります。再帰はありません。

アルゴリズム

すべての単語をハッシュセットに入れ、最も長い単語の長さ 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]

落とし穴と境界ケース

誤答の多くは、早すぎる段階で1つの切り方に決めてしまうか、失敗を記憶しない探索を行うことから生じます。

貪欲に分割する。最長の単語を先に取ると、carpetal は carpet に分割され、残りは al になりますが、car + petal ならうまくいきます。最短の単語を先に取ると、sunflowerseed で失敗します。
s のすべての文字が、いずれかの単語に含まれていることだけを確認する。単語が aaaa と aa の場合、どの断片も長さが偶数なので、7文字の aaaaaaa は分割できません。
メモに true の答えだけを保存する。true なら、その時点で探索は終了します。繰り返しの処理が発生するのは false の分岐なので、それらを保存しないメモでは計算量が指数的なままです。
要素数が1つ足りないテーブルを作る。canEnd[i] は先頭から i 文字についての値であり、0と n の両方が有効なので、要素数は n + 1 個必要です。
単語が残りの文字数より長い場合、たとえば単語 abc と ab を比べるときに、s の末尾を越えて比較する。文字を比較する前に長さを確認してください。
LuaとRでは、文字列の位置は1から始まります。文字eで終わる長さ k の断片は、文字 e-k+1 から始まります。

よくある質問4

Word Break の時間計算量はどれくらいですか？

ハッシュセットを使ったボトムアップのテーブルは、O(m × L + n × L²)時間で実行されます。ここで、nはsの長さ、mは単語数、Lは最長の単語の長さです。セットの構築では各単語を1回ずつ読み込み、n個の位置それぞれで、長さが最大L文字の部分文字列を最大L個検索します。代わりに各位置ですべての単語を比較すると、計算量はO(n × m × L)です。メモ化なしの単純な再帰は指数時間になります。

Word Break で貪欲法が失敗するのはなぜですか？

貪欲なルールは1つの単語を選ぶと、決して選び直しません。最長優先ではcarpetalをcarpetとalに分割しますが、car + petalならうまくいきます。最短優先ではsunflowerseedをsun + flowに分割し、erseedで行き詰まります。動的計画法は、分割によって到達できるすべての位置を保持するため、正しい位置を見失うことがありません。

Word Breakは動的計画法の問題ですか、それともグラフの問題ですか？

どちらの見方でも機能します。動的計画法としては、canEnd[i]は最初のi文字を分割できるかどうかを答え、小さな接頭辞から構築されます。グラフとしては、各インデックスがノードで、iからjまでの文字が単語を形成するときにiからjへの辺があります。そして、ノード0からノードnに到達できるかどうかを調べます。訪問済み集合を使った幅優先探索でも、表と同じ処理ができます。

真または偽を返す代わりに、すべての文を一覧表示するにはどうすればよいですか？

バックトラッキングを使います。各インデックスで当てはまる単語をすべて試し、残りの部分に対して再帰しながら、文を組み立てていきます。各インデックスについて文のリストを記憶しておけば、同じ残りの部分を解くのは一度だけです。まず真偽値テーブルを実行し、分割できない文字列は探索をスキップします。文の数は指数関数的に増える可能性があるため、出力のサイズによって実行時間が決まります。

Python

def wordBreak(s, wordDict):
    # ここにコードを書いてください

テストケース

ケース1

ケース2

ケース3

入力

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

期待値

true

Word Break

関数

制約

例

ヒント

解説

すべての単語をすべての位置で試す

メモ化を使った再帰

ハッシュセットを使って接頭辞をボトムアップで処理する

落とし穴と境界ケース

よくある質問4

似た問題