Word Break (LeetCode 139): Pythonでの動的計画法ソリューション

Word Break（LeetCode 139）は、文字列を、辞書に載っている単語だけを使って分割できるかどうかを判定する問題です。すっきりした答えは、接頭辞に対する動的計画法です。ある接頭辞は、それより短い「構築可能な接頭辞」の後ろに辞書の単語が続いていれば構築できます。さかのぼって調べる範囲を制限すれば、計算量は O(n × L) になります（L は最長の単語の長さ）。

問題

文字列 s と単語のリスト wordDict が与えられたとき、s を1つ以上の辞書の単語に分割できるなら true を返します。単語は何度でも再利用してかまいません。

面接官に確認すべきこと：辞書に重複が含まれ得るか、空になり得るか、文字列は空でないことが保証されているか。（制約は問題ページで確認しましょう。）

力まかせの解法

文字列の先頭に一致する最初の単語をすべて試し、残りに対して再帰します。"aaaaaaaaaab" のような文字列と単語 a、aa、aaa を考えると、再帰は同じ接尾辞を何度も訪れるため、時間は指数関数的になります。解決策は、各開始位置ごとに答えを記録しておくことです。

アプローチ1：メモ化を伴うトップダウン

can(start) を、start から始まる接尾辞を分割できるかどうかと定義します。結果をキャッシュします。

from functools import lru_cache

def word_break_memo(s, word_dict):
    words = set(word_dict)

    @lru_cache(maxsize=None)
    def can(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in words and can(end):
                return True
        return False

    return can(0)

n 個の開始位置はそれぞれ1回だけ解かれ、各位置は最大 n 個の終了位置を試し、そのたびにスライスと集合の検索を行います。これは O(n²) 回の検索、各スライスの生成コストを数えるなら O(n³) の文字操作になります。空間はキャッシュと再帰のために O(n) です。

アプローチ2：ボトムアップの動的計画法

dp[i] を、最初の i 文字を分割できるなら true とします。dp[0] は true です。空の接頭辞には単語が不要だからです。各終了位置について、dp[start] が true で s[start:end] が単語であるような開始位置を探します。

def word_break(s, word_dict):
    words = set(word_dict)
    max_len = max((len(w) for w in words), default=0)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for end in range(1, len(s) + 1):
        for start in range(max(0, end - max_len), end):
            if dp[start] and s[start:end] in words:
                dp[end] = True
                break
    return dp[len(s)]

start を直近 max_len 個の位置に制限することが重要です。辞書の単語は最長の単語より長くなり得ないので、それより長いスライスを調べる意味はありません。これにより内側のループは最大 L ステップになり、全体として O(n × L) 回の検索になります。

トレース

s = "leetcode" と ["leet","code"] の場合：dp[0] は true。dp[0] が true で "leet" が単語なので、dp[4] が true になります。dp[4] が true で "code" が単語なので、dp[8] が true になります。答えは dp[8] で、true です。

よくある間違い

• 単語を再利用できることを忘れる。
• ある接頭辞が単語になった時点で true を返してしまう。文字列全体を覆う必要があります。
• max_len の制限なしにすべてのスライスを生成する。正しいですが、長い文字列では遅くなります。
• 辞書を集合に変換するのが遅すぎる、あるいは変換しない。そのため各検索がリストを走査してしまいます。

テストすべきエッジケース

面接での説明の仕方

1. 力まかせの解法と、なぜ作業が繰り返されるのかを述べる。
2. 部分問題を述べる：長さ i の接頭辞は構築できるか？
3. 漸化式を言葉で述べ、それからボトムアップ版をコード化する。
4. max_len の制限に触れ、計算量を示す。
5. 面接官が再帰を好むなら、メモ化版を提示する。

公開前に、上記の両方のバージョンを、20,000 個のランダムな小さい入力に対する力まかせ探索と、表にある3つの例でテストしました。こうした簡単なランダムチェックは、練習するときの良い習慣です。

関連する練習

計算量の用語についてはBig O チートシートを、次に何を練習すべきかについてはLeetCode Blind 75 リストを、練習の進め方についてはコーディング面接アシスタントガイドをご覧ください。

コードを書きながら、自分のアプローチを声に出して説明しましょう。文字起こしを見れば、コードを書く前に重要な観察を述べたかどうかがわかります。ライブの評価では、AI ツールに関する雇用主のルールに従ってください。