Python의 특수 등가 문자열 그룹

<시간/>

A라는 문자열 배열이 있다고 가정합니다. S로 한 번 이동하면 S의 짝수 인덱스 문자 2개 또는 S의 홀수 인덱스 문자 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"]와 같으면 출력은 3이 됩니다. 한 그룹은 ["abcd", " cdab", "cbad"], 이는 모두 쌍별 특수 동등물이고 다른 문자열은 모두 쌍별 특수 동등물이 아니기 때문입니다. 다른 두 그룹도 있습니다. ["xyzz", "zzxy"] 및 ["zzyx"]입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

코드:=새로운 세트
A의 각 단어에 대해 다음을 수행합니다.
- code :=짝수 위치 인덱스가 있는 두 문자열과 홀수 위치 인덱스가 있는 다른 문자열 연결
- 코드에 코드 추가
반환 코드 크기

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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