[leetcode #49] Group Anagrams

Problem

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"]]

Constraints:

・ 1 <= strs.length <= 10⁴
・ 0 <= strs[i].length <= 100
・ strs[i] consists of lower-case English letters.

Idea

직관적으로 풀면 아주 쉬운 문제다. 우선 Input으로 들어온 string을 정렬하고 별도의 string array로 저장한다. Input string을 다시 탐색하면서 정렬한 string을 key로 넣고, input string을 value인 list에 더하면 된다. 마지막으로 map의 값들을 ArrayList로 만들어 리턴하기만 하면 된다.

1. Input으로 들어온 String을 정렬한다.
2. 정렬한 String을 HashMap의 key로, Input string을 value로 넣는다.
3. map의 value들 (String List)을 element로 하는 List를 만들어 리턴한다.

Solution

    public List<List<String>> groupAnagrams(String[] strs) {
	String[] sorted = new String[strs.length];

	
	for (int i=0; i < strs.length; i++) {
	    char[] charArray = strs[i].toCharArray();

	    Arrays.sort(charArray);
	    sorted[i] = new String(charArray);
	}

	Map<String, List<String>> map = new HashMap<>();

	for (int i=0; i < strs.length; i++) {
	    if (!map.containsKey(sorted[i]))
	        map.put(sorted[i], new ArrayList<>());
	    map.get(sorted[i]).add(strs[i]);
        }

	return new ArrayList<>(map.values());
    }

별 생각없이 풀면 결과는 안 좋게 마련이다. Runtime이야 그렇다쳐도 Memory Usage는 분포도에서 보이지도 않는다.😭 좀 더 생각을 해보니 loop를 두 번 돌 필요없이 한 번만 돌아도 원하는 결과를 얻을 수 있다는 사실을 깨달았다. 하지만 loop를 하나로 합쳐도 Runtime과 Memory Usage 둘 모두 큰 향상을 보이지 않는다. 어차피 루프를 여러 번 돌아도 O(n)이라는 사실에는 변함이 없기 때문일 것이다. 어떻게 하면 5ms 정도의 결과를 얻을 수 있을지 궁금해지는 밤이다.

Reference

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