-
[LeetCode] Group Anagrams알고리즘 2019. 10. 29. 16:37
문제
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
Counting: https://github.com/chi3236/algorithm/blob/master/LeetCode_GroupAnagrams_count.cpp
'알고리즘' 카테고리의 다른 글
[LeetCode] Maximum Subarray (0) 2019.10.29 [LeetCode] Pow(x, n) (0) 2019.10.29 [LeetCode] Permutations (0) 2019.10.28 [LeetCode] Wildcard Matching (0) 2019.10.24 [LeetCode] Trapping Rain Water (0) 2019.10.23