Pythonで最長の減少単語チェーンの長さを求めるプログラム

有効な単語のリストと文字列 s が与えられたとき、s から始めて1文字ずつ削除しながら、その各段階でも有効な単語になるように辿れる「減少単語チェーン」のうち、最も長いものの長さを求める問題です。

たとえば、入力が words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]、s = "limit" の場合、出力は 4 になります。これは「limit」を出発点として、「limit」→「limi」→「lii」→「li」というチェーンが作れるためです。

解き方のアプローチ

この問題は再帰呼び出しを使うことでシンプルに解けます。基本的な流れは以下のとおりです。

• solve() 関数を定義します。引数として words と s を受け取ります。
• max_num := 0 で初期化します。
• words 内の各単語 i について次を繰り返します。
  • i が s と一致する場合、j を 0 から s の長さまで動かしながら、j 番目の文字を取り除いた新しい文字列に対して solve() を再帰的に呼び出し、「1 + 戻り値」と現在の max_num の大きい方を max_num に代入します。
• 最後に max_num を返します。

Pythonでの実装例

class Solution:
   def solve(self, words, s):
      max_num = 0
      for i in words:
         if i == s:
            for j in range(len(s)):
               max_num = max(1 + self.solve(words, s[:j] + s[j + 1 :]), max_num)
      return max_num

ob = Solution()
words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"
print(ob.solve(words, s))

入力

["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"],"limit"

出力

4

アルゴリズムのポイント

このコードでは、現在の文字列 s が単語リストに含まれているかどうかを毎回確認しています。一致する単語が見つかった場合は、すべての位置について1文字を削除した文字列を生成し、それに対して再帰的に同じ処理を適用します。一致する単語が存在しない状態では max_num が 0 のまま返されるため、チェーンが途切れた時点で探索が自動的に打ち切られます。

なお、単語数や文字列の長さが大きくなると計算量が急増します。その場合は functools.lru_cache などでメモ化を行うことで、同じ文字列に対する重複計算を避け、処理を大幅に高速化できます。