[HashMap/Set][Medium] 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

 

Q. 두 문장 word1과 word2가 주어진 다고 할때 두 string이 close한지 판단하라. 아래와 같은 조건일때 close하다고 한다. 

 - 문장안에서 문자끼리 서로 치환된 상태. 

 - 문자는 달라도 등장 빈도가 같은 상태. 

 

Solution.

  두 조건에서 첫번째는, 결국 등장하는 캐릭터들이 frequency에 관계없이 같은지를 묻는 것이며, 두번째 조건은 frequency에서 등장하는 문자에 관계 없이 해당 횟수가 일치하는지를 뭍는 것이다. 

 두번째 조건에서 횟수 일치를 확인하기 위해서는 수를 동일한 조건으로 늘여놓아서 같은지 확인해야하는데 가장 좋은 방법은 정렬이다. 

 따라서 이 문제는 정렬로 인해 최소 O(N x LogN)의 TC를 요구하게 되는데, 해답을 보아도 결국 한번의 정렬 정도는 필요한 것으로 보인다. 

 

bool closeStrings(string word1, string word2) {
        
       if (word1.size() != word2.size())
            return false;

        map<char, int> freqMap1, freqMap2;
        for (int k = 0; k < word1.size(); ++k)
        {
            freqMap1[word1[k]]++;
            freqMap2[word2[k]]++;
        }	
        
		map<char, int>::iterator it1 = freqMap1.begin();
        map<char, int>::iterator it2 = freqMap2.begin();
        vector<int> vFreq1, vFreq2;
        for (; it1 != freqMap1.end(); ++it1, ++it2)
        {
            if (it1->first != it2->first)
                return false;

            vFreq1.push_back(it1->second);
            vFreq2.push_back(it2->second);
        }
        sort(vFreq1.begin(), vFreq1.end());
        sort(vFreq2.begin(), vFreq2.end());

        for (int k = 0; k < vFreq1.size(); ++k)
        {
            if (vFreq1[k] != vFreq2[k])
                return false;
        }
        return true;
    }