[Algorithm] Leetcode 1657 Determine if Two Strings Are Close

문제 링크

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

문제 풀이

접근법

일단 연산 가능한 option이 두 가지 정도 있는데, 적용할 알고리즘을 작성할까 고민하다가 무조건 안되는 케이스부터 제끼고 시작해야겠다는 생각이 들었다.

아래와 같은 케이스는 무조건 변환이 불가능하다.
1. 문자열의 길이가 다를때
2. 문자의 집합이 다를 때 (word1 = "abc", word2 = "abq")
3. 문자의 종류 별 개수의 집합(?) 이 다를 때

그래서 일단 위 조건을 차례대로 검사해보고, 안되는 케이스가 있으면 그 때 생각해보자는 생각으로 구현해서 돌렸는데 정답이었다.

python

class Solution:
    def makeDictionary(self, words: str) -> dict:
        word_dict = {}
        for word in words:
            if word not in word_dict:
                word_dict[word] = 0
            word_dict[word] += 1
        return word_dict

    def closeStrings(self, word1: str, word2: str) -> bool:

        if len(word1) != len(word2):
            return False

        # 구성 검사하기
        word1_dict = self.makeDictionary(word1)
        word2_dict = self.makeDictionary(word2)

        if set(word1_dict.keys()) != set(word2_dict.keys()):
            return False

        if sorted(word1_dict.values()) != sorted(word2_dict.values()):
            return False

        return True

C++

#include <vector>
#include <unordered_map>
class Solution {
public:
    unordered_map<char, int> makeDictionary(string words) {
        unordered_map<char, int> word_dict;
        for (auto& word: words) {
            if (word_dict.find(word) == word_dict.end()) {
                word_dict[word] = 0;
             }
            word_dict[word]++;
        }
        return word_dict;
    }
    bool closeStrings(string word1, string word2) {
        if (word1.length() != word2.length()) 
            return false;
        
        unordered_map<char, int> word1_dict = makeDictionary(word1);
        unordered_map<char, int> word2_dict = makeDictionary(word2);

        vector<char> word1_keys, word2_keys;
        vector<int> word1_values, word2_values;
        unordered_map<char, int>::iterator iter;

        for (iter = word1_dict.begin(); iter != word1_dict.end(); iter++) {
            word1_keys.push_back(iter->first);
            word1_values.push_back(iter->second);
        }

        for (iter = word2_dict.begin(); iter != word2_dict.end(); iter++) {
            word2_keys.push_back(iter->first);
            word2_values.push_back(iter->second);
        }

        sort(word1_keys.begin(), word1_keys.end());
        sort(word2_keys.begin(), word2_keys.end());

        if (word1_keys != word2_keys)
            return false;

        sort(word1_values.begin(), word1_values.end());
        sort(word2_values.begin(), word2_values.end());

        if (word1_values != word2_values) 
            return false;

        return true;
    }
};

근데 나 웰케 하위 구간에 있냐 .. ㅠㅠ