algoadvance

Leetcode 49. Group Anagrams

Problem Statement

Given an array of strings, you need to 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

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

Constraints:

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

Clarifying Questions

1. Q: Can the input array contain empty strings?
   • A: Yes, it can contain empty strings.
2. Q: Are all characters in the strings lowercase English letters?
   • A: Yes, all characters are lowercase English letters.
3. Q: Is the order of groups or the order within groups important in the output?
   • A: No, the order in the output does not matter.

Strategy

The key concept to solve this problem is to categorize words based on sorted versions of themselves, as the sorted string of all anagrams will be identical.

1. Sort Each String: Convert each string into a sorted version of itself.
2. Use Hash Map: Use a hash map to group the strings. The key will be the sorted string, and the value will be a list of strings that, when sorted, match the key.

Steps

1. Initialize an empty hash map where the key is a string and the value is a vector of strings.
2. Iterate through each string in the input list:
   • Sort the string.
   • Use the sorted string as a key in the hash map, and append the original string to the vector corresponding to that key.
3. Collect all values from the hash map and return them as the result.

Code

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> anagram_groups;
    
    for (string s : strs) {
        string sorted_s = s;
        sort(sorted_s.begin(), sorted_s.end());
        anagram_groups[sorted_s].push_back(s);
    }
    
    vector<vector<string>> result;
    for (auto& pair : anagram_groups) {
        result.push_back(pair.second);
    }
    
    return result;
}

Time Complexity

• Sorting Each String: Sorting takes O(k log k) time for each string where k is the maximum length of a string.
• Total Sorting Time: O(n * k log k), where n is the number of strings.
• Constructing the Hash Map: O(n * k) to iterate through all the strings and insert them into the map.
• Collecting Results: O(n) to collect all the groups from the hash map.

Overall, the time complexity is dominated by the sorting step:

• Total Time Complexity: O(n * k log k)

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?