Pythonで単語リスト内の異なる回転グループの数を求めるプログラム

問題の概要

文字列には、そのすべての一意な回転をまとめた「回転グループ」が存在するとします。たとえば入力が "567" の場合、この文字列は "675" や "756" に回転でき、これらはすべて同じ回転グループに属します。

ここで、文字列のリスト words が与えられたとき、各単語を回転グループごとに分類し、グループの総数を求める必要があります。

たとえば、words = ["xyz", "ab", "ba", "c", "yzx"] の場合、出力は 3 になります。これは次の3つの回転グループが存在するためです。

• ["xyz", "yzx"]
• ["ab", "ba"]
• ["c"]

解法のアプローチ

この問題を解くために、以下の手順に従います。

• s: 新しい集合（セット）を作成します
• ct: カウンターを 0 で初期化します
• words 内の各要素 i について、以下を処理します：
  • i が集合 s に含まれていない場合は、ct を 1 増やします
  • j を 0 から i の長さまで繰り返し、以下を実行します：
    • temp := i のインデックス j から末尾までの部分文字列と、先頭から j までの部分文字列を連結したもの
    • temp を集合 s に追加します
• 最後に ct を返します

つまり、各単語から生成されるすべての回転パターンをあらかじめ集合に登録しておき、まだ登録されていない単語が出てきたタイミングでのみカウントを増やすことで、同一の回転グループに属する重複を効率よく除外できます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
   def solve(self, words):
      s=set()
      ct=0
      for i in words:
         if i not in s:
            ct+=1
         for j in range(len(i)):
            s.add(i[j:]+i[:j])
      return ct
ob = Solution()
print(ob.solve(["xyz", "ab", "ba", "c", "yzx"]))

入力

["xyz", "ab", "ba", "c", "yzx"]

出力

3

計算量について

各単語の長さを L、単語の総数を N とすると、すべての回転パターンを生成して集合へ追加する処理の時間計算量は O(N × L²) となります。また、保存された回転パターンの分だけ空間計算量も必要です。それでも、すべての単語ペアを直接比較する方法（O(N² × L)）よりも効率的にグループ数を判定できる点が、この手法の大きな利点です。