Skip to content

Files

49

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Sep 13, 2023

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:

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

Example 2:

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

Example 3:

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

 

Constraints:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lower-case English letters.

Companies:
Amazon, Microsoft, Goldman Sachs, eBay, Apple, BlackRock, Facebook, Paypal, Uber, Yandex, Salesforce, Walmart Labs, Twilio, Two Sigma, Google, VMware, Snapchat, Splunk, Atlassian, Citadel

Related Topics:
Hash Table, String, Sorting

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/group-anagrams/
// Author: github.com/lzl124631x
// Time: O(NWlogW)
// Space: O(NW)
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& A) {
        unordered_map<string, vector<string>> m;
        for (auto &s : A) {
            auto key = s;
            sort(begin(key), end(key));
            m[key].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto &[key, strs] : m) ans.push_back(strs);
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/group-anagrams/
// Author: github.com/lzl124631x
// Time: O(NWlogW)
// Space: O(N)
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& A) {
        unordered_map<string, int> m;
        vector<vector<string>> ans;
        for (auto &s : A) {
            auto key = s;
            sort(begin(key), end(key));
            if (!m.count(key)) {
                m[key] = ans.size();
                ans.emplace_back();
            }
            ans[m[key]].push_back(s);
        }
        return ans;
    }
};