Nhóm chuỗi tương đương đặc biệt trong Python

Giả sử chúng ta có một mảng các chuỗi được gọi là A. Một lần di chuyển vào S bao gồm hoán đổi hai ký tự chẵn được lập chỉ mục bất kỳ của S hoặc bất kỳ hai ký tự được lập chỉ mục lẻ nào của S.

Bây giờ, hai chuỗi S và T là tương đương đặc biệt nếu sau bất kỳ số lần di chuyển nào lên S, S giống với T. Vì vậy, nếu S ="zzxy" và T ="xyzz" là tương đương đặc biệt vì chúng ta có thể thực hiện các bước di chuyển như "zzxy" thành "xzzy" thành "xyzz" hoán đổi S [0] và S [2], sau đó là S [1] và S [3].

Bây giờ, một nhóm các chuỗi tương đương đặc biệt từ A là một tập hợp con không rỗng của A sao cho -

Trong mọi cặp chuỗi trong nhóm là tương đương đặc biệt và nhóm là bất khả thi lớn nhất (không có chuỗi S không nằm trong nhóm sao cho S đặc biệt tương đương với mọi chuỗi trong nhóm đó) Chúng ta phải tìm số nhóm các chuỗi tương đương đặc biệt từ A.

Vì vậy, nếu đầu vào là ["abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"], thì đầu ra sẽ là 3, vì một nhóm là ["abcd", " cdab "," cbad "], vì chúng đều là các chuỗi tương đương đặc biệt theo từng cặp và không chuỗi nào khác là tất cả các chuỗi đặc biệt tương đương với các chuỗi này. Ngoài ra còn có hai nhóm khác. Đây là ["xyzz", "zzxy"] và ["zzyx"].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• mã:=một bộ mới
• đối với mỗi từ trong A, thực hiện
  • code:=nối hai chuỗi với chỉ số vị trí chẵn và một chuỗi khác với chỉ số vị trí lẻ
  • thêm mã vào các mã
• trả về kích thước của mã

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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"]))

Đầu vào

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

Đầu ra

3