【Python】リスト内の「連結語」の個数を数える方法をトライ木とDFSで解説

文字列のリストが与えられたとき、そのリスト内の他の単語を連結することで作られる単語がいくつあるかを求める問題を考えてみましょう。連結の際には単語を何度でも再利用でき、連結回数にも制限はありません。

例えば、入力が words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"] の場合を考えます。このとき出力は 2 になります。なぜなら、「helloworld」は「hello」と「world」の連結であり、「worldfamous」は「world」と「famous」の連結で作られているからです。

解決のためのアプローチ

この問題は、トライ（Trie）木と深さ優先探索（DFS）を組み合わせることで効率的に解けます。全体の流れは以下の通りです。

1. トライ木の構築

• trie: 新しいマップ（辞書）を用意する
• リスト内の各単語 word について:
  • layer := trie
  • 単語内の各文字 w について:
    • w が layer に存在しなければ、layer[w] に新しいマップを作成する
    • layer := layer[w]
  • 単語の終端を示すため layer["*"] := 空タプル を設定する

2. DFS関数の定義

引数として word（調査対象の単語）と num_concatenated_words（これまでに連結した単語の数）を受け取る関数 dfs() を定義します。

• layer := trie
• 単語の各位置 i と文字 w について:
  • "*" が layer に存在する場合（＝そこまでが辞書内の単語である場合）:
    • dfs(word[i:], num_concatenated_words + 1) が True を返せば、残りの部分も連結で構成できるため True を返す
  • w が layer に存在しなければ False を返す
  • layer := layer[w]
• 最後まで到達し、かつ "*" が layer に存在し、num_concatenated_words >= 1 ならば True を返す
• それ以外は False を返す

3. メイン処理

• count := 0
• リスト内の各単語について count += dfs(word, 0) を実行する
• count を返す

それでは、実際のコードを見てみましょう。

実装例

class Solution:
   def solve(self, words):
      trie = {}
      for word in words:
         layer = trie
         for w in word:
            if w not in layer:
               layer[w] = {}
            layer = layer[w]
         layer["*"] = ()

      def dfs(word, num_concatenated_words):
         layer = trie

         for i, w in enumerate(word):
            if "*" in layer:
               if dfs(word[i:], num_concatenated_words + 1):
                  return True
            if w not in layer:
               return False
            layer = layer[w]

         if "*" in layer and num_concatenated_words >= 1:
            return True
         return False

      count = 0
     for word in words:
      count += dfs(word, 0)
   return count

ob = Solution()
words = ["hello", "world", "helloworld", "famous", "worldfamous", "programming"]
print(ob.solve(words))

入力

["hello", "world", "helloworld", "famous", "worldfamous", "programming"]

出力

2

このアルゴリズムでは、まずすべての単語をトライ木に登録し、その後にDFSで各単語を分割できるかどうかを再帰的に確認しています。num_concatenated_words カウンタにより、「単語そのもの」ではなく「少なくとも2つ以上の単語の連結」であることを正しく判定している点がポイントです。計算量は単語数と長さに依存しますが、トライ木による前方一致検索のおかげで、素朴な全組み合わせチェックよりも大幅に高速化されています。