LeetCode Problem

Problem Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Examples

Input: strs = ['eat','tea','tan','ate','nat','bat']
Output: [['eat','tea','ate'],['tan','nat'],['bat']]

Input: strs = ['']
Output: [['']]

Input: strs = ['a']
Output: [['a']]

Constraints

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

Follow-up

Approach to Solve

Use a hash map to group anagrams by their sorted form.

Code Implementation

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = defaultdict(list)
        for word in strs:
            sorted_word = ''.join(sorted(word))
            anagrams[sorted_word].append(word)
        return list(anagrams.values())

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = new String(ca);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (const string& s : strs) {
            string sorted = s;
            sort(sorted.begin(), sorted.end());
            map[sorted].push_back(s);
        }
        vector<vector<string>> result;
        for (const auto& pair : map) {
            result.push_back(pair.second);
        }
        return result;
    }

Explanation

This solution uses a hash map to group anagrams by their sorted form. Here's a detailed explanation of the algorithm:

Initialize an empty hash map to store the groups of anagrams.
Iterate through each string in the input list strs:
- Sort the characters of the string.
- Use the sorted string as the key in the hash map.
- Add the original string to the list associated with this key.
After processing all strings, the hash map will contain all anagrams grouped by their sorted forms.
Return the values of the hash map as a list of lists of strings.

The time complexity is O(N * K log K), where N is the number of strings and K is the maximum length of a string in strs. This is because for each string, we sort it, which takes O(K log K) time, and we do this for N strings. The space complexity is O(N * K) to store the groups of anagrams in the hash map.

Complexity

Time Complexity: O(N * K log K), where N is the number of strings and K is the maximum length of a string in strs.
Space Complexity: O(N * K)

LeetSolved

Group Anagrams