[LeetCode] 49. Group Anagrams

Posted on | In

Problem

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
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.

Explanation

  1. We want to put all same anagrams into a list, so we can sort all strings, then if two sorted strings are equal, then they have the same anagram.

  2. Iterating each string, we can get the string then make it as a char array then do sorting. We put the sorted string into a hashmap<String, List<String>> as key, and the original string as value.

  3. After finish iteration, we can retun the hashmap’s values as a new array list as the result.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) return res;
        HashMap<String, List<String>> hm = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String k = String.valueOf(arr);
            if (!hm.containsKey(k)) {
                hm.put(k, new ArrayList<String>());
            }
            hm.get(k).add(str);
        }
        return new ArrayList<List<String>>(hm.values());
    }
}