Pythonで単語リストから最長の接頭辞（プレフィックス）連鎖を求める方法

この記事では、Pythonを使って「単語リストの中から、前の単語が次の単語の接頭辞（プレフィックス）になっており、次の単語にはちょうど1文字だけ新しい文字が追加されている」という条件を満たす最長の連鎖（シーケンス）の長さを求めるプログラムを紹介します。

問題の概要

小文字の文字列からなるリスト w が与えられます。この中から、以下の条件を満たす最長のシーケンスを見つけ、その長さを返します。

• シーケンス内の各単語は、直前の単語の接頭辞である
• 次の単語は、前の単語にちょうど1文字追加したものになっている

例えば、入力が w = ["pqr", "pq", "m", "mn", "pqrs"] の場合、出力は 3 になります。これは ["pq", "pqr", "pqrs"] というシーケンスを作れるためです。それぞれの単語は前の単語に1文字ずつ追加されており、このシーケンスの長さは3です。

解法のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。手順は以下の通りです。

1. リスト w を辞書順にソートします。こうすることで、ある単語の接頭辞となる候補が必ずその単語より前に現れます。
2. デフォルト値が0の辞書（defaultdict(int)）として dp を用意します。dp[word] は「その単語で終わる最長連鎖の長さ」を表します。
3. 結果を格納する変数 res を0で初期化します。
4. ソート済みの各単語について、以下を処理します。
   • dp[word] = dp[word[:-1]] + 1：最後の1文字を除いた部分（＝接頭辞）での連鎖の長さに1を加えます。
   • res = max(res, dp[word])：これまでの最大値を更新します。
5. 最後に res を返します。

実装例

実際のPythonコードは以下のようになります。

from collections import defaultdict

def solve(w):
    w.sort()
    dp = defaultdict(int)
    res = 0
    for word in w:
        dp[word] = dp[word[:-1]] + 1
        res = max(res, dp[word])
    return res

w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))

入力

["pqr", "pq", "m", "mn", "pqrs"]

出力

3

計算量について

単語数を n、単語の最大長を L とすると、ソートに O(n log n × L)、DPのループ処理に O(n × L) の時間がかかります。全体の計算量は O(n log n × L) となり、効率的な解法と言えます。また、辞書 dp にはすべての単語を保存するため、空間計算量は O(n × L) です。

まとめ

リストを事前にソートしておくことで、「接頭辞となる単語は必ず先に処理済み」という性質を利用でき、シンプルなDPで最長の接頭辞連鎖を求められます。文字列操作と動的計画法を組み合わせた典型的な問題なので、ぜひ理解しておきましょう。