[LeetCode] 893. Groups of Special-Equivalent Strings

문제 출처: https://leetcode.com/problems/groups-of-special-equivalent-strings/

Groups of Special-Equivalent Strings - LeetCode

문제

문자열 배열 words가 주어진다.

 

s에서의 이동은 s의 두 개의 짝수(또는 홀수) 인덱스 문자의 위치를 바꾸는 것을 의미한다.

 

s에서 몇번의 이동을 거친 후에 두 문자열 s와 t가 동일하다면 특별 동등(special-equivalent) 이다.

 

예를 들어, s = "zzxy"이고 t = "xyzz"이면 s[0]와 s[2]를 바꾸고, s[1]과 s[3]을 바꾸는 것으로 "zzxy" -> "xzzy" -> "xyzz"로 s와 t는 특별 동등이다.

 

words에서 특별 동등 문자열의 그룹 은 words의 부분집합이며, 다음의 규칙을 따른다:

1. 그룹 내 문자열의 모든 쌍은 특별 동등이다.
2. 그룹은 가능한 큰 크기이다. (어떤 문자열 s가 어떤 그룹의 모든 문자열과 특별 동등이라면, 이 문자열은 반드시 해당 그룹에 속해야 한다.)

words에서 특별 동등 문자열의 그룹 수를 반환하라.

예제

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

Explanation: 
One group is ["abcd", "cdab", "cbad"], since they are all pairwise special equivalent, and none of the other strings are all pairwise special equivalent to these.

The other two groups are ["xyzz", "zzxy"] and ["zzyx"].  Note that in particular, "zzxy" is not special equivalent to "zzyx".

풀이

어떤 문자열 s와 t가 특별 동등하기 위한 조건을 생각해보면,

 

이동 행위가 새로운 문자를 추가하는 과정이 아니기 때문에 s와 t를 구성하는 문자는 완전히 동일해야 한다. 조금 더 깊게 생각해보면, 이동 행위는 짝수 인덱스끼리 혹은 홀수 인덱스끼리 스왑 하는 것이기 때문에, s와 t를 짝수 번대 문자열과 홀수 번대 문자열로 나눌 수 있고, 이들끼리의 문자 구성이 같아야 함을 유추할 수 있다.

 

간단한 예를 살펴보면 다음과 같다.

s = 'zzxy', t = 'xyzz'

s의 짝수 인덱스 문자열(s.even) = 'zx'
s의 홀수 인덱스 문자열(s.odd) = 'zy'

t의 짝수 인덱스 문자열(t.even) = 'xz'
t의 홀수 인덱스 문자열(t.odd) = 'yz'

s.even의 구성 == t.even의 구성
s.odd 구성 == t.odd의 구성

이를 기반으로 다음과 같은 알고리즘을 설계할 수 있다.

function numSpecialEquivGroups(words) {
    // 특별 동등 그룹의 대표 문자를 담을 집합 자료구조
    group = new Set();

    for (word of words) {

        // 짝수 인덱스 문자열과 홀수 인덱스 문자열을 담을 배열
        evenStr = '';
        oddStr = '';
        for (i = 0; i < word.length; i = i + 2) {

            evenStr += word[i];
            if (i+1 < word.length) oddStr += word[i+1];

        }

        // 문자열을 정렬 및 합쳐서 group에 삽입
        // 특별 동등한 관계라면 동일한 문자열이 만들어질 것임
        group.add(evenStr.sort() + oddStr.sort());
    }

    return group.size;
}

Github: 893.js

opwe37/Algorithm-Study