[LeetCode] Determine if Two Strings Are Close

https://leetcode.com/problems/determine-if-two-strings-are-close/description/?envType=study-plan-v2&envId=leetcode-75

 

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.

 

Example 1:
Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:
Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:
Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"
 

Constraints:
1 <= word1.length, word2.length <= 105
word1 and word2 contain only lowercase English letters.

 

---

 

영문 소문자로 이루어진 문자열 두 개가 주어지고, 두 개의 문자열이 가까운 관계인지 확인하는 문제다.

'가깝다' 는 건 아래의 두 가지 처리를 횟수 상관없이 거쳤을 때 두 문자열이 같아질 수 있다는 걸 의미한다.

1. 두 개의 문자 위치를 바꾼다.

2. 문자열을 이루는 문자 중 한 가지 모두를 다른 한 가지로 바꾼다.

(예시: abbbccc 가 있으면, a를 모두 c로, c를 모두 a로 바꿔 cbbbaaa 로 바꾼다.)

 

일단.. 두 문자열의 길이가 다르면 절대 같아질 수 없고, 

2번 처리로 문자열을 같게 만들려면 각 문자열을 이루는 문자 종류의 분포 수가 똑같아야 한다.

예를 들어서, aabbbc와 bbaaac는 각각 a:2, b:3, c:1 / b:2, a:3, c:1 의 분포로 이루어져 있다.

문자열끼리 서로 바꿔서 같아질 수 있으려면, 위 두가지 문자열처럼 각 문자열 내에 문자가 1,2,3개씩 있어야 한다.

그리고 문자열을 구성하는 문자의 종류가 동일해야 한다.

 

만약 a는 4개 있고, b는 3개, c는 1개 있는데 다른 문자열은 a가 3개, b가 3개, c가 2개 있다면

문자열의 총 길이는 같지만 문자열끼리 서로 개수를 바꾸는 것으로 두 문자열이 같아질 수 없다.

 

이 규칙을 기반으로 코드를 짰다~.~

const counts = (arr) => {
    const res = {};
    for (const char of arr){
        if(res[char]){
            res[char]++;
        }else{
            res[char] = 1;
        }
    }
    return res;
}

const closeStrings = function(word1, word2) {
    // 1.두 개의 문자 위치를 바꾸기
    // 2.한 가지의 문자 모두를 다른 문자로 바꾸기
    // 위 두 처리를 진행했을 때 word1과 word2가 동일해질 수 있다면 close 하다고 본다.
    if (word1.length !== word2.length){
        return false;
    }
    // 2가 가능하려면, 각기 다른 문자의 수의 분포가 똑같아야 한다.
    const obj1 = counts(word1);
    const obj2 = counts(word2);

    // 문자열을 구성하는 문자의 종류가 동일해야 한다.
    if(Object.keys(obj1).sort().join() !== Object.keys(obj2).sort().join()){
        return false;
    }
  
    if(Object.values(obj1).sort().join() !== Object.values(obj2).sort().join()){
        return false;
    }
    
    return true;
};

 

sort를 최대한 안 쓰고 싶었는데 내가 생각한 게 맞나 싶어서 일단 확인해보려고 작성한 코드~.~

일단 각 문자가 몇개씩 있는지 객체로 만들고, 그 문자열을 구성하는 문자의 종류(객체의 key들)가 동일한지 확인한다.

그 이후에는 각 문자의 수 분포가 동일한지 확인한다. 

이대로 제출하니 통과는 됐지만 아무래도 효율이 좀 떨어졌다.

 

그렇게 훔쳐본 효율 1등 코드에서 (그러고보니) 영문자가 26가지라는 힌트를 얻고 다시 푼 코드.

const closeStrings = function(word1, word2) {
    // 1.두 개의 문자 위치를 바꾸기
    // 2.한 가지의 문자 모두를 다른 문자로 바꾸기
    // 위 두 처리를 진행했을 때 word1과 word2가 동일해질 수 있다면 close 하다고 본다.
    if (word1.length !== word2.length){
        return false;
    }
    let counts1 = new Array(26).fill(0);
    let counts2 = new Array(26).fill(0);
    
    // 영문은 26개라는 점을 활용해서.. charCodeAt으로 알파벳 위치별 수를 카운트한다.
    for(let i=0; i < word1.length; i++){
        counts1[word1.charCodeAt(i) - 97]++;
        counts2[word2.charCodeAt(i) - 97]++;
    }

    // 동일한 문자 종류로 이루어져 있는지 확인한다.
    for(let i=0; i < 26; i++){
        if((counts1[i] == 0) !== (counts2[i] == 0)){
            return false;
        }
    }

    // 소팅해서 비교한다.
    counts1.sort();
    counts2.sort();

    for(let i=0; i < 26; i++){
        if(counts1[i] !== counts2[i]){
            return false;
        }
    }

    return true;
};

 

이렇게 하면 그냥 문자열 길이만큼 한 바퀴 돌고, 26번씩 두바퀴만 돌면 끝난다! 와우!