[리트코드] 49. Group Anagrams (HashTable)

문제 정보

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

문제 풀이

해시테이블을 이용해서 문제를 해결한다.

1. 묶여야 되는 값들의 공통 요소를 키로 선정한다. (풀이에서는 alphabetically sorted된 string으로 선정)

2. 해시테이블 별 값을 리스트로 묶고 해당 리스트들을 전체 리스트에 삽입하여 반환 

 

Writeup

public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs)
    {
        IList<IList<string>> answerList = new List<IList<string>>();
        Dictionary<string, List<string>> hashtable = new Dictionary<string, List<string>>();

        foreach (string str in strs)
        {
            string key = new string(str.OrderBy(x => x).ToArray()); //Get key by sorting

            if (!hashtable.ContainsKey(key)) // Add key and value if there is no key
            {
                hashtable.Add(key, new List<string>());
                hashtable[key].Add(str);
            }
            else // Add value to list if there is key already
            {
                hashtable[key].Add(str);
            }         
        }

        foreach(string key in hashtable.Keys)
        {
            answerList.Add(hashtable[key]);
        }

        return (IList<IList<string>>) answerList;
    }
}