Anagrammes du groupe Leetcode
Lien ici
Je vais inclure une solution en Python et C ++ et vous pourrez en examiner une. Je suis surtout intéressé par la révision du code C ++, une chose que j'ai récemment commencé à apprendre; ceux qui ne connaissent pas C ++ peuvent consulter le code Python. Les deux solutions partagent une logique similaire, la révision s'appliquera donc à toutes.
Énoncé du problème
Étant donné un tableau de chaînes de chaînes, regroupez les anagrammes. Vous pouvez renvoyer la réponse dans n'importe quel ordre. Un anagramme est un mot ou une phrase formé en réorganisant les lettres d'un mot ou d'une phrase différent, en utilisant généralement toutes les lettres originales exactement une fois.
Exemple:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Les deux solutions impliquent la création d'un mappage des caractères de mot classés par ordre alphabétique au mot correspondant et chaque mot rencontré qui correspond, est ajouté au groupe correspondant. Et comme il a été suggéré plus tôt dans mes articles précédents de ne pas se fier aux statistiques de leetcode car elles sont inexactes, j'ai chronométré les solutions c ++ et python pour 1000000 d'exécutions sur le même ensemble de mots pour voir ce qui se passe. Étonnamment, la solution python surpasse la solution c ++ presque par 2x. Les temps résultants ~ = 10, 20 secondes pour python et c ++ respectivement lorsqu'ils sont exécutés sur mon i5 2,7 GHZ mbp. Étant donné que les deux implémentations sont presque similaires, C ++ ne devrait-il pas être 10 fois plus rapide que 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)
Résultats:
[['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";
}
Résultats:
abets baste beats
tabu
actress casters
allergy gallery largely
Calculating time for 1000000 runs ...
22 seconds
Réponses
C ++
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
contains
effectue une recherche du mot dans word_groups
. Puis operator[]
fait cette même recherche une deuxième fois.
Nous pouvons remplacer ce qui précède par juste:
word_groups[sorted_word].push_back(word);
( operator[]
insère une valeur construite par défaut (c'est-à-dire vide vector<std::string>
) si elle n'est pas présente dans la carte).
Nous n'avons pas besoin de copier la word_groups
carte dans un vecteur pour la renvoyer get_groups()
. Nous pouvons simplement renvoyer la carte elle-même.
Ensuite, dans la fonction principale, nous l'itérons avec:
for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...
Nous n'avons pas besoin de stocker la chaîne elle-même dans la carte, nous pouvons stocker l'index de la chaîne dans le vecteur d'entrée. (ie map<string, vector<std::size_t>>
).