[LeetCode] 1657. Determine if Two Strings Are Close

https://leetcode.com/problems/determine-if-two-strings-are-close/description/

Determine if Two Strings Are Close - LeetCode

leetcode - Determine if Two Strings Are Close

문제 유형 : 문자열 처리, 해시

문제 난이도 : Medium

 

문제

Two strings are considered close if you can attain one from the other using the following operations:

• Operation 1: Swap any two existing characters.
  • For example, abcde -> aecdb
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
  • For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

 

 

두 개의 문자열에서 한 문자열이 아래의 연산들을 몇 번이고 사용해서 다른 한 문자열로 만들 수 있으면 두 문자열은 close한다고 하자.

• 연산 1: 두 개의 존재하는 문자의 위치를 바꾸기
• 연산 2: 존재하는 문자들의 개수를 서로 바꾸기

 

두 문자열 word1과 word2가 주어진다. word1과 word2가 close하면 true를, 아니라면 false를 반환하라.

 

 

풀이

문자들의 순서는 어떻게든 재배치 할 수 있으므로, 문자열에서 각 문자가 있는지의 여부와, 문자들의 개수가 어떻게 되는지만 따지면 된다.

두 문자열 중에서 한 문자열만 특정 문자열을 가지고 있으면 만들 수 없다.

같은 문자들을 가지고 있어야 하고, 각 문자들의 개수들이 서로 대응되어야 한다.

(abbccc = 1개짜리 문자 덩어리 1개, 2개짜리 문자 덩어리 1개, 3개짜리 문자 덩어리 1개)

 

이를 어떻게 구현할 수 있을까?

알파벳 소문자만 올 수 있으므로, 길이가 26이고 기본값이 0인 배열을 두 개 만든다.

각 문자열의 문자들의 빈도를 저장하기 위해서이다.

두 배열을 채워주고, 두 배열을 비교해 보자.

두 배열 중에서 한 쪽은 없고, 한 쪽은 가지고 있는 문자가 있다면, false이다.

두 배열을 정렬하고 두 배열이 다르다면, 연산 2를 통해서 만들 수 없다. 

그러므로 정렬된 두 배열을 비교해주면 된다.

 

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        vector<int> freq1(26, 0);
        vector<int> freq2(26, 0);

        if(word1.size() != word2.size()) return false;

        for(int i = 0; i < word1.size(); i++) {
            freq1[word1[i]-97]++;
            freq2[word2[i]-97]++;
        }

		// 둘 중 하나만 있으면 안됨.
        for(int i = 0; i < 26; i++) {
            if((freq1[i] == 0 && freq2[i] != 0) || (freq1[i] != 0 && freq2[i] == 0)) return false;
        }

		// 같은 문자들의 개수들의 집합이 다르면 안됨.
        sort(freq1.begin(), freq1.end());
        sort(freq2.begin(), freq2.end());

        return freq1 == freq2;
    }
};