Pythonの等価ペアを使って文字列が回文かどうかを判定する方法

問題の概要

小文字の英字からなる文字列 s と、ペアのリスト pairs が与えられているとします。pairs の各要素は2つの文字列 [a, b] から構成され、文字 a と b は同じものであるとみなされます。

例えば、[a, b] と [b, c] という2つのペアが存在する場合、「a と b は等価」であり「b と c も等価」であるため、推移的に「a と c も等価」と考えることができます。また、任意の値は常にそれ自身と等価です。このような等価関係のもとで、文字列 s が回文として成立するかどうかを判定するのが本問題です。

入力例と考え方

s = "raceckt"、pairs = [["r", "t"], ["a", "k"], ["z", "x"]] の場合、出力は True になります。「a = k」「r = t」という等価関係が成り立つため、対応する位置の文字を置き換えれば、文字列を回文である "racecar" にすることができるからです。

解法のアプローチ

この問題は、グラフの深さ優先探索（DFS）を利用することで効率的に解けます。手順は以下の通りです。

• 重複要素を含みうる隣接リスト g（defaultdict(list)）を作成します。
• 重複を排除した隣接リスト G（defaultdict(set)）も用意します。
  • pairs 内の各 (x, y) について、g[x] と g[y] に互いの文字を追加します。
• dfs() 関数を定義します（引数：a、so_far）。
• まず a を so_far に追加します。
• g[a] 内の各要素について、まだ so_far に存在しなければ dfs を再帰的に呼び出します。
• メイン処理では、g 内の各 key に対して dfs(key, G[key]) を実行し、各文字から到達可能な「等価な文字の集合」を構築します。
• i を 0 から len(s) // 2 - 1 までループします。
  • s[i] == s[-1-i]、または s[i] が G[s[-1-i]] に含まれる、または s[-1-i] が G[s[i]] に含まれる場合は continue で次へ進みます。
  • いずれの条件も満たさない場合は False を返します。
• すべてのチェックを通過すれば True を返します。

実装例

理解を深めるために、以下のPythonコードをご覧ください。

from collections import defaultdict
def solve(s, pairs):
   g = defaultdict(list)
   G = defaultdict(set)
   for x, y in pairs:
      g[x].append(x)
      g[y].append(y)
      g[x].append(y)
      g[y].append(x)

   def dfs(a, so_far):
      so_far.add(a)
      for elem in g[a]:
         if elem not in so_far:
            dfs(elem, so_far)

   for key in g:
      dfs(key, G[key])

   for i in range(0, len(s) // 2):
      if s[i] == s[-1 - i] or (s[i] in G[s[-1 - i]] or s[-1 - i] in G[s[i]]):
         continue
      else:
         return False
   return True

s = "raceckt"
pairs = [["r", "t"], ["a", "k"], ["z", "x"]]
print(solve(s, pairs))

入力

"raceckt", [["r", "t"], ["a", "k"], ["z", "x"]]

出力

True

まとめ

この手法では、与えられた等価ペアをもとにグラフを構築し、DFSによって各文字が属する等価クラス（同値グループ）を求めています。その後、文字列の先頭と末尾から中央に向かって対称位置の文字を比較し、両者が同一または等価であれば回文として成立すると判断できます。計算量は DFS の探索と文字比較により、文字数やペア数に対して線形時間で処理可能な効率的なアプローチです。