# Leetcode group anagrams

I'll include a solution in Python and C++ and you can review one. I'm mostly interested in reviewing the C++ code which is a thing I recently started learning; those who don't know C++ can review the Python code. Both solutions share similar logic, so the review will apply to any.

## Problem statement

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:

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


Both solutions involve creating a mapping from word characters ordered alphabetically to corresponding word and each word encountered that is a match, is added to the corresponding group. And since it was suggested earlier in my previous posts not to rely on leetcode's stats because they are inaccurate, I timed both c++ and python solutions for 1,000,000 runs on the same set of words to see what comes up. Surprisingly, python solution outperforms the c++ solution almost by 2x. The resulting times ~= 10, 20 seconds for python and c++ respectively when run on my i5 2.7 GHZ mbp. Given that both implementations are almost similar, shouldn't c++ be 10x times faster than python?

group_anagrams.py

from collections import defaultdict
from time import perf_counter

def group(words):
groups = defaultdict(lambda: [])
for word in words:
groups[tuple(sorted(word))].append(word)
return groups.values()

def time_grouping(n, words):
print(f'Calculating time for {n} runs ...')
t1 = perf_counter()
for _ in range(n):
group(words)
print(f'Time: {perf_counter() - t1} seconds')

if __name__ == '__main__':
w = [
'abets',
'baste',
'beats',
'tabu',
'actress',
'casters',
'allergy',
'gallery',
'largely',
]
print(list(group(w)))
time_grouping(1000000, w)


Results:

[['abets', 'baste', 'beats'], ['tabu'], ['actress', 'casters'], ['allergy', 'gallery', 'largely']]
Calculating time for 1000000 runs ...
Time: 8.801584898000002 seconds


group_anagrams.h

#ifndef LEETCODE_GROUP_ANAGRAMS_H
#define LEETCODE_GROUP_ANAGRAMS_H

#include <vector>
#include <string>

std::vector<std::vector<std::string>> get_groups(const std::vector<std::string> &words);

#endif //LEETCODE_GROUP_ANAGRAMS_H


group_anagrams.cpp

#include "group_anagrams.h"
#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>

std::vector<std::vector<std::string>>
get_groups(const std::vector<std::string> &words) {
std::map<std::string, std::vector<std::string>> word_groups;
std::vector<std::vector<std::string>> groups;
for (const auto &word: words) {
auto sorted_word = word;
std::sort(sorted_word.begin(), sorted_word.end());
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
}
groups.reserve(word_groups.size());
for (auto const &imap: word_groups)
groups.push_back(imap.second);
return groups;
}

int main() {
std::vector<std::string> words{
"abets", "baste", "beats", "tabu", "actress", "casters", "allergy",
"gallery", "largely"
};
auto groups = get_groups(words);
for (const auto &group: groups) {
for (const auto &word: group)
std::cout << word << ' ';
std::cout << '\n';
}
size_t n_times{1000000};
std::cout << "\nCalculating time for " << n_times << " runs ..." << '\n';
auto t1 = std::chrono::high_resolution_clock::now();
while (n_times > 0) {
get_groups(words);
n_times--;
}
auto t2 = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::seconds>(
t2 - t1).count();
std::cout << duration << " seconds";
}


Results:

abets baste beats
tabu
actress casters
allergy gallery largely

Calculating time for 1000000 runs ...
22 seconds

• I think its better to split as 2 quivalent questions, each for specific language. Nov 23 '20 at 8:32
• About Python's solution, defaultdict(lambda: []) can be shorten to defaultdict(list).
– Marc
Nov 23 '20 at 8:36
• @hjpotter92 I don't think that is necessary unless there are significant differences between both versions. I've been notified previously by other members of the community and I indicated the same. Nov 23 '20 at 8:37

## C++

    if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}


contains does a search for the word in word_groups. Then operator[] does that same search a second time.

We can replace the above with just:

    word_groups[sorted_word].push_back(word);


(operator[] inserts a default-constructed value (i.e. an empty vector<std::string>) if it isn't present in the map).

We don't need to copy the word_groups map into a vector to return it from get_groups(). We can just return the map itself.

Then in the main function we'd iterate it with:

for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...


We don't need to store the string itself in the map, we can store the index of the string in the input vector. (i.e. map<string, vector<std::size_t>>).