[C++] LeetCode : Group Anagrams

Question

문자열로 이루어진 배열이 주어졌을 때, Anagrams인 문자열끼리 그룹핑하는 문제이다. Anagram을 어떤 순서로 리턴하여도 상관이 없다.

Anagram: word 혹은 phase의 문자를 재배열하여 형성된 word 혹은 phase. 일반적으로 모든 original 문자를 한 번만 사용한다. 예를 들어 "abc"의 Anagram은 "bca", "bac", "cab", "cba", "acb" 이 있다.

제약사항 :
배열의 총 길이는 최소 1 ~ 최대 104이다.
문자열 길이는 최소 0 ~ 최대 100 이다.
문자열은 모두 소문자로 이루어져 있다.

 

---

Solution

• 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR))
   배열의 최대길이를 n이라 하고, 가장 긴 문자열의 길이를 s라 가정했을 때,
  최소 한번씩은 다 보아야 하기 때문에 BCR은 O(ns)이다.
  
  
• 고려사항
  문자열의 길이가 다를 수 있다.
  
  
• Solution 1 (Brute force)
  각 문자열을 기준으로 Anagram 여부를 비교하여 묶고, 묶이지 않은 문자열을 기준으로 묶는 작업을 끝까지 한다.
  두 문자열을 정렬해서 각 문자를 비교하는 과정으로 Anagram 여부를 판단한다고 하였을 때 정렬에 필요한 시간 복잡도는 O(nslogs) // s는 배열에서 가장 긴 문자열, n 은 배열의 길이
  anagram이 하나도 없다고 가정했을 때 전체 비교에 소요되는 시간은 O(1/2n^2) = O(n^2)
  따라서 O(nslogs) + O(n^2) * O(s) = O(n^2s * nslogs)
  
  
• Soultion 2 (Solution 1 개선) : Anagram 여부를 각 문자의 등장 빈도수로 판단
  Anagram 인지 판단하는 방법은 정렬하지 않고 각 문자열 안의 문자 등장 횟수가 같으면 anagram이라고 볼 수 있다. 따라서 solution 1의 정렬 과정을 skip 해도 됨으로 총 시간 복잡도는 O(s) * O(n^2) = O(s * n^2)

class Solution {
public:
    bool isAnagram(string s1, string s2) {
        int char_count[26] = { 0 };
        for (int i = 0; i < s1.size(); i++) {
            char_count[s1[i] - 'a']++;
            char_count[s2[i] - 'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (char_count[i] != 0) return false;
        }
        return true;
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret_vec;
        int group_index = 0;

        for (auto str : strs) {
            bool flag = false;
            for (int i = 0; i < ret_vec.size(); i++) {
                if (ret_vec[i][0].size() != str.size()) continue;

                if (isAnagram(str, ret_vec[i][0])) {
                    ret_vec[i].push_back(str);
                    flag = true;
                    break;
                }
            }

            if (flag == false) {
                vector<string> new_anagram;
                new_anagram.push_back(str);
                ret_vec.push_back(new_anagram);
            }
        }

        return ret_vec;
    }
};

 

• Soultion 3 (Solution 2 개선) : Anagram 여부를 각 문자의 등장 빈도수 자체를 Hash의 key값으로 이용
  제약사항에서 문자열은 소문자로만 이루어져 있기 때문에, 빈도수 자체를 Hash의 key값으로 사용한다면, 따로 찾는 과정 없이 한번 읽는 것만으로 grouping을 할 수 있다. 이때의 시간 복잡도는 O(ns)

class Solution {
public:
    string make_string_key(string s) {
        int char_count[26] = { 0 };
        for (int i = 0; i < s.size(); i++) {
            char_count[s[i] - 'a']++;
        }

        string ret = "";
        for (int i = 0; i < 26; i++) {
            ret += ((char)i + char(char_count[i]));
        }
        return ret;
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret_vec;
        map<string, vector<string>> anagram_group;

        for (auto str : strs) {
            string key = make_string_key(str);
            if (anagram_group.find(key) == anagram_group.end()) {
                vector<string> new_group;
                anagram_group[key] = new_group;
                anagram_group[key].push_back(str);
            }
            else {
                anagram_group[key].push_back(str);
            }
        }

        auto iter = anagram_group.begin();
        while (iter != anagram_group.end()) {
            ret_vec.push_back(iter->second);
            ++iter;
        }

        return ret_vec;
    }
};

 

문제 출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/778/

Explore - LeetCode

 

 

* 본 포스트 관련된 지적 및 조언은 모두 환영합니다.