Pythonで単語リストがしりとりの輪（円環）になるか判定するプログラム

問題の概要

単語のリストが与えられたとき、それらの単語をすべて1回ずつ使って「しりとりの輪（円環）」を作れるかどうかを判定する問題です。単語Aを単語Bの直前に連結できるのは、Aの末尾の文字とBの先頭の文字が一致する場合のみです。なお、最初と最後の単語の接続は考慮しません。

例えば、次のような入力を考えてみましょう。

words = ["ant", "dog", "tamarind", "nausea", "gun"]

この場合、以下のように単語を並べると輪になります。

• ant → tamarind（t → t）
• tamarind → dog（d → d）
• dog → gun（g → g）
• gun → nausea（n → n）
• nausea → ant（a → a）

したがって、出力は True となります。

解法のアプローチ：オイラー閉路として捉える

この問題は、文字をノード、単語を「先頭文字から末尾文字への辺」とする有向グラフに言い換えることで解けます。すべての単語をちょうど1回ずつ使って一つの輪を作ることは、グラフ上のすべての辺をちょうど1回ずつ通る閉路（オイラー閉路）が存在することと同じ意味です。

有向グラフにオイラー閉路が存在するための条件は次の2つです。

• すべてのノードにおいて入次数と出次数が一致している
• グラフが連結である（すべての辺が同一の連結成分に属する）

これらの条件を、次数の比較とDFS（深さ優先探索）によって確認していきます。

アルゴリズムの手順

• graph := 隣接リストとして新しい辞書を用意
• seen := 訪問済みノードを記録する新しい集合を用意
• inDegree := 入次数を数えるカウンタを用意
• outDegree := 出次数を数えるカウンタを用意
• 各単語 word に対して、以下を実行：
  　・start := word[0]（先頭文字）
  　・end := word[-1]（末尾文字）
  　・graph[start] の末尾に end を追加
  　・outDegree[start] を +1
  　・inDegree[end] を +1
• outDegree 内の各ノード node に対して、outDegree[node] と inDegree[node] が一致しない場合は False を返す
• 最初の単語の先頭文字 words[0][0] から dfs() を開始
• len(seen) が len(graph) と一致すれば True、そうでなければ False を返す

dfs() 関数の定義

• 引数 node を seen に追加する
• graph[node] 内の各子ノード child に対して、まだ訪問していなければ再帰的に dfs(child) を呼び出す

Pythonでの実装例

それでは、実際のコードを見てみましょう。collections.defaultdict で隣接リストを、collections.Counter で次数を管理すると簡潔に書けます。

import collections
class Solution:
    def solve(self, words):
        self.graph = collections.defaultdict(list)
        self.seen = set()
        inDegree = collections.Counter()
        outDegree = collections.Counter()
        for word in words:
            start = word[0]
            end = word[-1]
            self.graph[start].append(end)
            outDegree[start] += 1
            inDegree[end] += 1
        for node in outDegree:
            if outDegree[node] != inDegree[node]:
                return False
        self.dfs(words[0][0])
        return len(self.seen) == len(self.graph)
    def dfs(self, node):
        self.seen.add(node)
        for child in self.graph[node]:
            if child not in self.seen:
                self.dfs(child)
ob = Solution()
print(ob.solve(["ant","dog","tamarind","nausea","gun"]))

入力

["ant","dog","tamarind","nausea","gun"]

出力

True

計算量と補足

グラフの構築は単語数 N に対して O(N)、DFSによる到達確認も各ノード・各辺を高々1回処理するため全体の時間計算量は O(N)、空間計算量も O(N) となります。

なお、このコードでは「入次数と出次数の一致」を全ノードで確認した後、DFSで最初の単語の先頭文字から到達できるノード数を数えています。ただし厳密には、孤立した文字ノードや複数の連結成分が存在するケースをより正確に扱うには、「すべての辺が同一の連結成分に属するか」を辺ベースで確認する追加チェックを組み合わせると安全です。