Pythonで解くワードブレイク問題：動的計画法による文字列分割の判定方法

空でない文字列 s と、空でない単語のリストからなる辞書 wordDict が与えられたとき、s を1つ以上の辞書内の単語を空白で区切った並びに分割できるかどうかを判定する問題を考えてみましょう。この問題には、次のようなルールがあります。

• 辞書内の同じ単語は、分割の中で何度でも再利用してよい。
• 辞書には重複する単語が含まれていないものと仮定してよい。

たとえば、文字列 s = "applepenapple"、辞書 = ["apple", "pen"] の場合、出力は true になります。これは、s を "apple pen apple" という形に分割できるためです。なお、単語 "apple" は2回使われていますが、ルール上は再利用が許されているので問題ありません。

アルゴリズムの手順

この問題は、動的計画法（DP）を使うことで効率的に解くことができます。基本的な発想は、「部分文字列が辞書の単語そのものであるか」、あるいは「より短い部分文字列同士に分けて、それぞれが分割可能であるか」を順番に記録していくことです。具体的な手順は以下の通りです。

• n × n のサイズのDPテーブルを定義します（n は文字列 s の長さ）。すべての要素を false で初期化します。
• i を 1 から s の長さまで繰り返します。
  • j を 0 から s の長さ − i まで繰り返します。
    • 部分文字列 s[j 〜 j+i] が辞書に含まれている場合は、dp[j][j+i−1] を True にします。
    • そうでない場合は、k を j+1 から j+i−1 まで繰り返し、dp[j][k−1] と dp[k][j+i−1] がどちらも True になれば、dp[j][j+i−1] を True にします。
• 最後に dp[0][sの長さ − 1] を返します。これが文字列全体が分割可能かどうかを表します。

実装例（Python）

理解を深めるために、以下の実装を見てみましょう。

class Solution(object):
    def wordBreak(self, s, wordDict):
        dp = [[False for i in range(len(s))] for x in range(len(s))]
        for i in range(1, len(s)+1):
            for j in range(len(s)-i+1):
                if s[j:j+i] in wordDict:
                    dp[j][j+i-1] = True
                else:
                    for k in range(j+1, j+i):
                        if dp[j][k-1] and dp[k][j+i-1]:
                            dp[j][j+i-1] = True
        return dp[0][len(s) - 1]

ob1 = Solution()
print(ob1.wordBreak("applepenapple", ["apple", "pen"]))

入力

"applepenapple"
["apple", "pen"]

出力

true

まとめ

このアルゴリズムでは、すべての部分文字列について「分割可能かどうか」を段階的に求めていくため、時間計算量は O(n³)、空間計算量は O(n²) となります。部分文字列を直接辞書と照合するシンプルなアプローチに加えて、すでに計算済みの小さい区間の結果を組み合わせることで、複雑な分割パターンも正しく判定できるのがポイントです。