Pythonで文字列が指定した単語リストに分解できるか判定するプログラム

問題概要

単語のリストと、スペースを含まない文字列 s が与えられたとき、その文字列をリスト内の単語の組み合わせに分解できるかどうかを判定します。

たとえば、words = ["love", "python", "we", "programming", "language"]、s = "welovepythonprogramming" の場合、「we love python programming」というように分解できるため、出力は True になります。

解法のアプローチ

この問題は、再帰（バックトラッキング）を用いて解くことができます。具体的な手順は以下の通りです。

• words を、重複のない単語からなるセット（set）に変換します
• 関数 rec() を定義します。引数として現在の位置 i を受け取ります
• i が文字列 s の長さと等しい場合、True を返します（すべての文字を消費できたことを意味します）
• acc を空文字列として初期化します
• j を i から s の長さまで順にループさせます
  • acc に s[j] を連結していきます
  • acc が words に含まれる場合、rec(j + 1) を呼び出し、その結果が True であれば True を返します
• ループが終了しても分解方法が見つからなければ、False を返します
• メイン処理から rec(0) を呼び出し、その結果を返します

以下の実装例を見ると、より理解しやすいでしょう。

実装例

class Solution:
   def solve(self, words, s):
      words = set(words)

      def rec(i=0):
         if i == len(s):
            return True
         acc = ""
         for j in range(i, len(s)):
            acc += s[j]
            if acc in words:
               if rec(j + 1):
                  return True
         return False

      return rec()
     
ob = Solution()
words = ["love", "python", "we", "programming", "language"]
s = "welovepythonprogramming"
print(ob.solve(words, s))

入力

["love", "python", "we", "programming", "language"], "welovepythonprogramming"

出力

True

計算量と改善のポイント

このシンプルな再帰実装では、最悪の場合に指数時間 O(2ⁿ) かかる可能性があります。これは、同じ位置からの探索が何度も繰り返されるためです。

実務では、一度調べた開始位置の結果をキャッシュするメモ化（memoization）を追加すると、計算量を大幅に削減できます。Python では functools.lru_cache デコレータや辞書を使って簡単に実装でき、各位置についての判定が一度だけ行われるようになるため、効率的に動作します。