Anagramy grupowe Leetcode
Link tutaj
Dołączę rozwiązanie w Pythonie i C ++ i możesz je przejrzeć. Najbardziej interesuje mnie przeglądanie kodu C ++, czego ostatnio zacząłem się uczyć; Ci, którzy nie znają C ++, mogą przejrzeć kod Pythona. Oba rozwiązania mają podobną logikę, więc recenzja będzie dotyczyć każdego.
Opis problemu
Mając tablicę ciągów łańcuchów, zgrupuj razem anagramy. Możesz zwrócić odpowiedź w dowolnej kolejności. Anagram to słowo lub fraza utworzona przez przestawienie liter innego słowa lub frazy, zazwyczaj używając wszystkich oryginalnych liter dokładnie raz.
Przykład:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Oba rozwiązania polegają na utworzeniu mapowania ze znaków słownych uporządkowanych alfabetycznie na odpowiadające im słowo, a każde napotkane słowo będące dopasowaniem jest dodawane do odpowiedniej grupy. A ponieważ zasugerowałem wcześniej w moich poprzednich postach, aby nie polegać na statystykach leetcode, ponieważ są one niedokładne, ustawiłem czas w rozwiązaniach C ++ i Python na 1000000 uruchomień na tym samym zestawie słów, aby zobaczyć, co się pojawi. Zaskakujące jest, że rozwiązanie Pythona przewyższa rozwiązanie C ++ prawie dwukrotnie. Wynikowe czasy ~ = 10, 20 sekund odpowiednio dla pythona i c ++, gdy są uruchamiane na moim i5 2,7 GHZ mbp. Biorąc pod uwagę, że obie implementacje są prawie podobne, czy C ++ nie powinien być 10 razy szybszy niż 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)
Wyniki:
[['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";
}
Wyniki:
abets baste beats
tabu
actress casters
allergy gallery largely
Calculating time for 1000000 runs ...
22 seconds
Odpowiedzi
C ++
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
contains
wyszukuje słowo w word_groups
. Następnie przeprowadza operator[]
to samo wyszukiwanie po raz drugi.
Powyższe możemy zastąpić tylko:
word_groups[sorted_word].push_back(word);
( operator[]
wstawia domyślnie skonstruowaną wartość (tj. pustą vector<std::string>
), jeśli nie ma jej na mapie).
Nie musimy kopiować word_groups
mapy do wektora, aby ją zwrócić get_groups()
. Możemy po prostu zwrócić samą mapę.
Następnie w funkcji głównej powtórzymy ją za pomocą:
for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...
Nie musimy przechowywać samego ciągu w mapie, możemy przechowywać indeks ciągu w wektorze wejściowym. (tj map<string, vector<std::size_t>>
.).