</>Ali · LeetCode
#0049·MediumStrings

Group Anagrams

LeetCode #49 · Medium · Strings · C++ solution with worked-out approach and complexity analysis.

View on LeetCodeSource on GitHub

Approach

Hash Map with Sorted String as Key

Key insight

Anagrams will produce the same string when sorted. For example, "eat", "tea", "ate" all become "aet" when sorted.

Strategy

  1. 1Create a hash map where the key is the sorted version of each string
  2. 2For each string in the input:
  3. 3Extract all values from the hash map to get grouped anagrams
Time
O(n * k log k)
n is the number of strings and k is the max length
Space
O(n * k)
to store all strings in the hash map
Problem description(from LeetCode)

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.

Examples

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

Constraints

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

C++ Solution

solution.cpp
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string> &strs) {
    unordered_map<string, vector<string>> mp;
    for (auto it = strs.begin(); it != strs.end(); it++) {
      string s = *it;
      sort(s.begin(), s.end());
      mp[s].push_back(*it);
    }
    vector<vector<string>> v;
    for (auto it = mp.begin(); it != mp.end(); it++) {
      v.push_back((*it).second);
    }

    return v;
  }
};

More Strings problems