Leetcode Amazon Interview Questions

Group Anagrams

Leetcode - No. 49

49 Group Anagrams

Given an array of strings, group anagrams together.

1
2
3
4
5
6
7
8
9
Example:

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

Problem Analysis

Each string has it’s own identified key, and we need to sort the string to clustering them into the correct group.

Algorithm Analysis

By switching String into a Character Array and sort that array to get a key String, we usd that key to identify the group. I have used that keyString to recognized if the string is the same as the previous one. If the string has existed in the Map, add that one into the List in the Map.

Time Complexity Analysis

Time: O(m * nlogn)
Space: O(Map)

Code Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        List<List<String>> results = new ArrayList<>();
        if(strs.length == 0) return results;
        
        for(int i = 0; i < strs.length; i++) {
            String currentString = strs[i];
            String currentKey = getStringKey(currentString); /* Sorting cause nlogn */
            
            if(!map.containsKey(currentKey)) {
                map.put(currentKey, new ArrayList<>());
            }
            map.get(currentKey).add(currentString);
        }
        
        for(String key : map.keySet()) {
            results.add(map.get(key));
        }
        
        // return new ArrayList<List<String>>(map.values());
        return results;
    }
    
    String getStringKey(String str) {
        char[] strs = str.toCharArray();
        Arrays.sort(strs);
        return new String(strs);
    }
}

FEATURED TAGS
Leetcode Amazon Interview Questions