Pythonの特別に同等の文字列のグループ

Aという文字列の配列があるとします。Sへの1つの移動は、Sの任意の2つの偶数のインデックス付き文字、またはSの任意の2つの奇数のインデックス付き文字の交換で構成されます。

ここで、2つの文字列SとTは、Sにいくつでも移動した後、SがTと同じである場合、特別に同等です。したがって、S="zzxy"とT="xyzz"の場合、移動を行う可能性があるため、特別に同等です。たとえば、「zzxy」から「xzzy」、「xyzz」のように、S[0]とS[2]を入れ替え、次にS[1]とS[3]を入れ替えます。

ここで、Aからの特別に同等の文字列のグループは、Aの空でないサブセットであり、-

グループ内の文字列のすべてのペアは特別に同等であり、グループは可能な最大サイズです（Sがそのグループ内のすべての文字列と特別に同等であるようなグループ内にない文字列Sはありません） Aからの特別に同等の文字列のグループ。

したがって、入力が["abcd"、 "cdab"、 "cbad"、 "xyzz"、 "zzxy"、 "zzyx"]の場合、1つのグループが["abcd"、 "であるため、出力は3になります。 cdab "、" cbad "]、これらはすべてペアワイズスペシャルと同等であり、他の文字列はすべてペアワイズスペシャルと同等ではないためです。他にも2つのグループがあります。これらは["xyzz"、 "zzxy"]、["zzyx"]です。

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

• コード：=新しいセット
• Aの各単語について、
  • code：=偶数の位置インデックスを持つ2つの文字列と、奇数の位置インデックスを持つ別の文字列を連結します
  • コードをコードに追加する
• コードのサイズを返す

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

例

class Solution:
   def numSpecialEquivGroups(self, A):
      codes = set()
      for word in A:
         code = ''.join(sorted(word[::2])) +''.join(sorted(word[1::2]))
         codes.add(code)
      return len(codes)
ob = Solution()
print(ob.numSpecialEquivGroups(["abcd","cdab","cbad","xyzz","zzxy","z
zyx"]))

入力

["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

出力

3