Pythonで解くWord Break II：メモ化再帰による単語分割パターンの全列挙

問題の概要

空でない文字列 s と、空でない単語のリストからなる辞書 wordDict が与えられます。文字列 s にスペースを挿入して文を構成し、文中のすべての単語が辞書内の有効な単語となるようにします。このとき、考えられるすべての文を見つけるのがこの問題の目的です。

たとえば、文字列が「appleraincoat」、辞書が ["app", "apple", "rain", "coat", "raincoat"] の場合、「apple rain coat」と「apple raincoat」という2通りの文が構成できます。

解法のアプローチ：メモ化再帰

この問題は、メモ化（memoization）を組み合わせた再帰的な探索によって効率よく解けます。同じ部分文字列に対する計算結果をキャッシュして再利用することで、無駄な再計算を排除できるのがポイントです。

アルゴリズムの手順

1. 計算結果をキャッシュするためのマップ memo を用意する。
2. 文字列 s と辞書 wordDict を引数に取るメソッド solve を定義する。
3. s が空文字列の場合は、空文字列を1つ含むリストを返す（再帰の終端条件）。
4. s がすでに memo に存在する場合は、memo[s] を返す（再計算しない）。
5. 結果を格納する配列 ret を作成する。
6. i を 1 から s の長さまで動かしながらループする。
   • s[:i]（先頭から i 文字目までの部分文字列）が wordDict に存在する場合、残りの s[i:] に対して solve を再帰的に呼び出す。
   • 各戻り値 j について、「s[:i] + 半角スペース + j」を連結し、前後の余分な空白を取り除いて ret に追加する。
7. memo[s] = ret として結果をキャッシュする。
8. memo[s] を返す。

実装例

以下はPythonでの実装例です。まず辞書を set に変換することで、単語の存在確認をO(1)で行えるようにしています。

class Solution(object):
    def wordBreak(self, s, wordDict):
        self.memo = {}
        wordDict = set(wordDict)
        return self.solve(s, wordDict)

    def solve(self, s, wordDict):
        if not s:
            return ['']
        if s in self.memo:
            return self.memo[s]
        ret = []
        for i in range(1, len(s) + 1):
            if s[:i] in wordDict:
                for j in self.solve(s[i:], wordDict):
                    ret.append((s[:i] + " " + j).strip())
        self.memo[s] = ret
        return self.memo[s]

ob = Solution()
print(ob.wordBreak("appleraincoat", ["app", "apple", "rain", "coat", "raincoat"]))

入力

"appleraincoat"
["app", "apple", "rain", "coat", "raincoat"]

出力

['apple rain coat', 'apple raincoat']

コードのポイントと計算量

• メモ化の効果： 同じ接尾辞（部分文字列）に対する分割候補を一度計算すれば、以降はキャッシュから即座に取得できます。これにより、素朴な再帰で発生する重複計算が完全になくなります。
• 終端条件： 空文字列に到達したときに [''] を返すことで、「ここで文が完結した」ことを表現しています。これにより呼び出し元で正しく1文として組み立てられます。
• 計算量： 分割結果の出力自体が指数個になり得るため、全体の計算量は最悪ケースで指数時間になります。ただし、メモ化により同じ部分問題の再計算が不要になるため、実行時間は大幅に改善されます。