Leetcode-Gruppenanagramme
Ich werde eine Lösung in Python und C ++ aufnehmen, und Sie können eine überprüfen. Ich bin hauptsächlich daran interessiert, den C ++ - Code zu überprüfen, was ich kürzlich gelernt habe. Wer C ++ nicht kennt, kann den Python-Code überprüfen. Beide Lösungen haben eine ähnliche Logik, sodass die Überprüfung für alle gilt.
Problemstellung
Gruppieren Sie die Anagramme bei einem Array von Strings strs. Sie können die Antwort in beliebiger Reihenfolge zurückgeben. Ein Anagramm ist ein Wort oder eine Phrase, die durch Neuanordnen der Buchstaben eines anderen Wortes oder einer anderen Phrase gebildet wird, wobei normalerweise alle Originalbuchstaben genau einmal verwendet werden.
Beispiel:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Bei beiden Lösungen wird eine Zuordnung von alphabetisch geordneten Wortzeichen zum entsprechenden Wort erstellt, und jedes gefundene Wort, das übereinstimmt, wird der entsprechenden Gruppe hinzugefügt. Und da in meinen vorherigen Beiträgen bereits früher vorgeschlagen wurde, sich nicht auf die Statistiken von Leetcode zu verlassen, weil diese ungenau sind, habe ich sowohl C ++ - als auch Python-Lösungen für 1.000.000 Läufe mit denselben Wörtern zeitlich festgelegt, um zu sehen, was auf mich zukommt. Überraschenderweise übertrifft die Python-Lösung die c ++ - Lösung fast um das Zweifache. Die resultierenden Zeiten ~ = 10, 20 Sekunden für Python bzw. C ++, wenn sie auf meinem i5 2.7 GHZ MBP ausgeführt werden. Sollte c ++ nicht zehnmal schneller sein als Python, da beide Implementierungen fast gleich sind?
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)
Ergebnisse:
[['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";
}
Ergebnisse:
abets baste beats
tabu
actress casters
allergy gallery largely
Calculating time for 1000000 runs ...
22 seconds
Antworten
C ++
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
contains
sucht nach dem Wort in word_groups
. Dann operator[]
wird dieselbe Suche ein zweites Mal durchgeführt.
Wir können das Obige durch nur ersetzen:
word_groups[sorted_word].push_back(word);
( operator[]
Fügt einen standardmäßig erstellten Wert (dh einen leeren Wert vector<std::string>
) ein, wenn er nicht in der Karte vorhanden ist.)
Wir müssen die word_groups
Karte nicht in einen Vektor kopieren , um sie zurückzugeben get_groups()
. Wir können einfach die Karte selbst zurückgeben.
Dann würden wir es in der Hauptfunktion wiederholen mit:
for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...
Wir müssen die Zeichenfolge selbst nicht in der Karte speichern, sondern können den Index der Zeichenfolge im Eingabevektor speichern. (dh map<string, vector<std::size_t>>
).