文字列をチェックするプログラムが回文であるか、Pythonで同等のペアを使用していないか

sという小文字のアルファベット文字列があり、「pairs」というペアのリストもあるとします。ペアの各要素には2つの文字列[a、b]があり、文字「a」と「b」は同じと見なされます。 [a、b]と[b、c]のように2つのペアがある場合、aとbは同等であり、bとcも同等であると言えます。したがって、aとcも同等です。そして、任意の値aまたはbはそれ自体と同等です。 sがパリンドロームであるかどうかを、与えられた同値関係でチェックする必要があります。

したがって、入力がs ="raceckt" pair =[["r"、 "t"]、["a"、 "k"]、["z"、 "x"]]の場合、出力は次のようになります。 beTrue、「a」=「k」および「r」=「t」であるため、文字列は回文である「レースカー」にすることができます。

これを解決するには、次の手順に従います-

• g：=リストに重複する要素が含まれている可能性があるグラフの隣接リスト
• G：=重複要素を含まないグラフの隣接リスト
  • ペアのx、yごとに、実行します
  • g [x]
  の最後にxを挿入します
  • g [y]
  の最後にyを挿入します
  • g [x]
  の最後にyを挿入します
  • g [y]
  の最後にxを挿入します
• 関数dfs（）を定義します。これには、so_farが必要です
• so_farにaを挿入
• g [a]の各要素について、実行します
  • elemがso_farにない場合は、
    • dfs（elem、so_far）
• メインの方法から、次の手順を実行します-
• gの各キーについて、
  • dfs（key、G [key]）
  • 0から（s / 2のサイズ）のフロアまでの範囲のiの場合、
    • s[i]がs[sizeof s -1-i]または（s[i]がG[s [size ofs-1-i]]またはs[-1-i]の場合in G [s [i]]）、次に
      • 次の反復に進む
    • それ以外の場合、
      • Falseを返す
• Trueを返す

例

理解を深めるために、次の実装を見てみましょう-

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