Nhóm chuỗi đặc biệt tương đương (Special-Equivalent Strings) trong Python

Giả sử ta có mảng chuỗi A. Một nước đi trên S là hoán đổi hai ký tự chỉ số chẵn bất kỳ của S, hoặc hai ký tự chỉ số lẻ bất kỳ.

Hai chuỗi S và T đặc biệt tương đương nếu sau bất kỳ số nước đi nào trên S, S giống T. Ví dụ S="zzxy", T="xyzz" đặc biệt tương đương vì có thể "zzxy" -> "xzzy" -> "xyzz" hoán đổi S[0] với S[2], rồi S[1] với S[3].

Nhóm chuỗi đặc biệt tương đương từ A là tập con không rỗng của A sao cho:

Mọi cặp chuỗi trong nhóm đặc biệt tương đương, và nhóm có kích thước lớn nhất (không có chuỗi S ngoài nhóm mà S đặc biệt tương đương với mọi chuỗi trong nhóm). Ta tìm số nhóm chuỗi đặc biệt tương đương từ A.

Ví dụ, ["abcd","cdab","cbad","xyzz","zzxy","zzyx"], đầu ra 3, nhóm ["abcd","cdab","cbad"], ["xyzz","zzxy"], ["zzyx"].

Giải quyết:

• codes := set mới
• for word in A, do
  • code := nối chuỗi chỉ số chẵn đã sort + chuỗi chỉ số lẻ đã sort
  • thêm code vào codes
• trả về kích thước codes

Xem triển khai:

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

Đầu vào

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

Đầu ra

3