Leetcode 그룹 애너그램
여기에 링크
저는 Python과 C ++로 된 솔루션을 포함 할 것이며 하나를 검토 할 수 있습니다. 저는 최근에 배우기 시작한 C ++ 코드를 검토하는 데 주로 관심이 있습니다. C ++를 모르는 사람들은 Python 코드를 검토 할 수 있습니다. 두 솔루션 모두 유사한 논리를 공유하므로 검토가 모두 적용됩니다.
문제 설명
문자열 strs의 배열이 주어지면 애너그램을 함께 그룹화합니다. 어떤 순서로든 답변을 반환 할 수 있습니다. Anagram은 일반적으로 모든 원래 문자를 정확히 한 번 사용하여 다른 단어 또는 구의 문자를 재정렬하여 형성된 단어 또는 구입니다.
예:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
두 솔루션 모두 알파벳순으로 정렬 된 단어 문자에서 해당 단어로의 매핑을 생성하고 일치하는 각 단어가 해당 그룹에 추가됩니다. 그리고 이전 게시물에서 leetcode의 통계가 정확하지 않기 때문에 의존하지 말라고 제안했기 때문에 동일한 단어 집합에서 1,000,000 회 실행되는 C ++ 및 Python 솔루션의 시간을 설정하여 무엇이 나오는지 확인했습니다. 놀랍게도 python 솔루션은 C ++ 솔루션보다 거의 2 배 더 우수한 성능을 보입니다. i5 2.7 GHZ mbp에서 실행될 때 결과 시간은 각각 파이썬과 C ++에 대해 ~ = 10, 20 초입니다. 두 구현이 거의 비슷하다는 점을 감안할 때 C ++가 파이썬보다 10 배 빠르지 않습니까?
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)
결과 :
[['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";
}
결과 :
abets baste beats
tabu
actress casters
allergy gallery largely
Calculating time for 1000000 runs ...
22 seconds
답변
C ++
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
contains에서 단어를 검색합니다 word_groups. 그런 다음 operator[]동일한 검색을 두 번 수행합니다.
위의 내용을 다음으로 대체 할 수 있습니다.
word_groups[sorted_word].push_back(word);
( 지도에없는 경우 operator[]기본 생성 된 값 (즉, 빈 vector<std::string>)을 삽입합니다 .)
word_groups에서 반환하기 위해지도를 벡터로 복사 할 필요가 없습니다 get_groups(). 지도 자체를 반환 할 수 있습니다.
그런 다음 주 함수에서 다음과 같이 반복합니다.
for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...
문자열 자체를 맵에 저장할 필요는 없으며 문자열의 인덱스를 입력 벡터에 저장할 수 있습니다. (예 map<string, vector<std::size_t>>).