Description

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:

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

Example 2:

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

Example 3:

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

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Solution

In this case, we want to group all anagrams into single List or array. All anagrams if sorted by their character will look exactly same. So, we can use this sorted word as the key for map and store all anagram words in the list as a value. If the string is sorted, the characters will always appear in the same order.

 1class Solution {
 2    public List<List<String>> groupAnagrams(String[] strs) {
 3        if (strs == null || strs.length == 0) {
 4            return new ArrayList<>();
 5        }
 6        Map<String, List<String>> groups = new HashMap<>();
 7        for (String str: strs) {
 8            char[] chars = str.toCharArray();
 9            Arrays.sort(chars);
10            String key = String.valueOf(chars);
11            if (!groups.containsKey(key)) {
12                groups.put(key, new ArrayList<>());
13            }
14            groups.get(key).add(str);
15        }
16        return new ArrayList<>(groups.values());
17    }
18}
  • Time Complexity: In this case, we iterate through strs array once to insert them into our map. For each insertion, we also have to sort each word in the strs array. Let’s assume that maximum length of the word in the input array is of length k. Then, this sorting would take at most O(k log k) time complexity. So, the overall time complexity is O(n * k log k)
  • Space Complexity: We will need to store all values of the strs array which would take O(n) and also keys in sorted manner which can take upto O(k). Overall, space complexity is O(n * k).