1
\$\begingroup\$

Link here

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think its better to split as 2 quivalent questions, each for specific language. \$\endgroup\$
    – hjpotter92
    Nov 23 '20 at 8:32
  • 1
    \$\begingroup\$ About Python's solution, defaultdict(lambda: []) can be shorten to defaultdict(list). \$\endgroup\$
    – Marc
    Nov 23 '20 at 8:36
  • \$\begingroup\$ @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. \$\endgroup\$ Nov 23 '20 at 8:37
1
\$\begingroup\$

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>>).

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.