[LeetCode] Group Anagrams

문제

Given an array of strings, group anagrams together.

Example:

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

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

Approach

각 string을 sort해보고 그 결과가 같으면 같은 그룹으로 묶는다. 이를 위해 map (혹은 unorderd_map)을 사용하였다.

시간복잡도는 총 string의 개수가 N개, string 하나의 최대 길이가 K일때 O(NKlogK)이다

 

Optimization

각 string을 sort하지 말고 어떤 알파벳이 몇 개씩 들어있는지를 세보고

구성이 같으면 같은 그룹으로 묶는다. 여기에도 역시 map이 사용되었다.

시간복잡도는 O(NK)이지만 실제 구현했을 때는 위 방법이 더 빨랐다.

 

Code

Sorting: https://github.com/chi3236/algorithm/blob/master/LeetCode_GroupAnagrams_SortString.cpp

chi3236/algorithm

Counting: https://github.com/chi3236/algorithm/blob/master/LeetCode_GroupAnagrams_count.cpp

chi3236/algorithm