Classic Interview 150 Questions P49: Group Anagrams

---

Timeline

Timeline

2025-11-13

init

Hash table

---

Problem:

P49 Group Anagrams

https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150

Brute force comparison TLE

Not only complex but also times out 😢😢😢

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

using std::vector;
using std::string;
using std::unordered_map;

class Solution {
    public:
	bool isAnagram(string s, string t)
	{
		if (s.size() != t.size()) {
			return false;
		}
		unordered_map<char, int> smap;
		for (char &ch : s) {
			smap[ch]++;
		}
		for (char &ch : t) {
			if (!smap.count(ch)) {
				return false;
			} else {
				smap[ch]--;
				if (smap[ch] < 0) {
					return false;
				}
			}
		}
		return true;
	}
	vector<vector<string> > groupAnagrams(vector<string> &strs)
	{
		vector<vector<string> > res;
		if (strs.empty()) {
			res.push_back(vector<string>());
			return res;
		}
		if (strs.size() == 1) {
			res.push_back(vector<string>(1, strs[0]));
			return res;
		}
		// First group by size
		vector<vector<string> > diff_size_strs;
		unordered_map<int, int> size2index;

		for (string &s : strs) {
			if (!size2index.count(s.size())) {
				vector<string> vec;
				vec.push_back(s);
				diff_size_strs.push_back(vec);
				size2index[s.size()] = diff_size_strs.size() - 1;
			} else {
				diff_size_strs[size2index[s.size()]].push_back(s);
			}
		}

		for (vector<string> &vec : diff_size_strs) {
			int n = vec.size();
			int i, j = n - 1;

			while (j >= 0) {
				vector<string> curr;
				string base = vec[j];
				curr.push_back(vec[j]);
				j--;
				for (i = 0; i <= j; i++) {
					if (isAnagram(base, vec[i])) {
						curr.push_back(vec[i]);
						swap(vec[i], vec[j]);
						j--;
						i--; //Recheck the current position
					}
				}
				res.push_back(curr);
			}
		}
		return res;
	}
};

Sorting + Hash Table

Use the sorted string of each string as the key of the hash table, and the value of the hash table is the original strings with the same key.

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

using std::vector;
using std::unordered_map;
using std::string;

class Solution {
    public:
        vector<vector<string> > groupAnagrams(vector<string> &strs)
        {
                vector<vector<string> > ret;
                unordered_map<string, vector<string> > umap;
                int i, n = strs.size();

                for (i = 0; i < n; i++) {
                        string curr = strs[i];
                        std::sort(curr.begin(), curr.end());
                        umap[curr].push_back(strs[i]);
                }

                for (auto &[_, vec] : umap)
                        ret.push_back(vec);

                return ret;
        }
};