[Hashmap][Medium] 49. Group Anagrams

https://leetcode.com/problems/group-anagrams/description

 

Q. 주어진 문자열 목록 strs 에 대해 서로 anagrams 인 것들에 대해 묶어서 출력하라. 

 

 

Solution

 여러 풀이가 있을 수 있다. 

 

 Frequency buffer를 사용하면, 각 문자당 freq buffer를 만들고, 

 해당 버퍼가 같다면, anagram 하다고 판단할 수 있다. 

 하지만 O(NxN)의 TC가 소요되고, 역시나 Time limitation 오류가 생긴다. 

 

 다른 접근을 해 본다. 

 문자를 같은 원리에 의해 재 조립하면, 같은 문자를 가진 단어는 같은 문자 순서를 가질 것이다.

 즉, string을 정렬해 본다. 

 

 정렬에 O(N x logN), map 비교에 N 즉, 최종 O(N x LogN)으로 이전 접근보다는 조금 더 빠르다. 

 

 정렬에 근거해 코드를 만든다. 

 

string SortString(string input)
{
    char[] characters = input.ToArray();
    Array.Sort(characters);
    return new string(characters);
}

public IList<IList<string>> GroupAnagrams(string[] strs) 
{
    Dictionary<string, List<int>> dictStrs = new Dictionary<string, List<int>>();
    for(int q = 0; q < strs.Length; ++q)
    {
        string word = SortString(strs[q]);
        if(!dictStrs.ContainsKey(word))
            dictStrs.Add(word, new List<int>());
        dictStrs[word].Add(q);
    }

    IList<IList<string>> ret = new List<IList<string>>();
    foreach(var key in dictStrs.Keys)
    {
        List<string> listStr = new List<string>();
        for(int q = 0; q < dictStrs[key].Count; ++q)
            listStr.Add(  strs[ dictStrs[key][q] ] );
        ret.Add(listStr);
    }
    return ret;
}

 

 

적절한 결과를 얻었다.

 

 

Note) 

 LINQ를 활용한 정렬 String.Concat(strs[q].OrderBy(c => c)); 를 사용했더니, 다소 느리게 나왔다. 

 Array sort를 우선해서 사용하는 것으로.