Đảo chữ cái nhóm Leetcode
Tôi sẽ đưa vào một giải pháp bằng Python và C ++ và bạn có thể xem lại một giải pháp. Tôi chủ yếu quan tâm đến việc xem lại mã C ++, đây là thứ mà tôi mới bắt đầu học gần đây; những người không biết C ++ có thể xem lại mã Python. Cả hai giải pháp chia sẻ logic tương tự, vì vậy việc xem xét sẽ áp dụng cho bất kỳ giải pháp nào.
Báo cáo vấn đề
Cho một mảng các chuỗi ký tự, hãy nhóm các ký tự đảo ngữ lại với nhau. Bạn có thể gửi lại câu trả lời theo bất kỳ thứ tự nào. Đảo chữ cái là một từ hoặc cụm từ được hình thành bằng cách sắp xếp lại các chữ cái của một từ hoặc cụm từ khác nhau, thường sử dụng tất cả các chữ cái gốc chính xác một lần.
Thí dụ:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Cả hai giải pháp đều liên quan đến việc tạo ánh xạ từ các ký tự từ được sắp xếp theo thứ tự bảng chữ cái đến từ tương ứng và mỗi từ gặp phải là một đối sánh, được thêm vào nhóm tương ứng. Và vì nó đã được đề xuất trước đó trong các bài viết trước của tôi là không dựa vào số liệu thống kê của leetcode vì chúng không chính xác, tôi đã hẹn giờ cho cả giải pháp c ++ và python cho 1.000.000 lượt chạy trên cùng một tập hợp từ để xem điều gì xuất hiện. Đáng ngạc nhiên là giải pháp python hoạt động tốt hơn giải pháp c ++ gần như gấp 2 lần. Thời gian kết quả ~ = 10, 20 giây cho python và c ++ tương ứng khi chạy trên mbp i5 2.7 GHZ của tôi. Cho rằng cả hai cách triển khai gần như tương tự nhau, thì c ++ có phải nhanh hơn python 10 lần không?
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)
Các kết quả:
[['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";
}
Các kết quả:
abets baste beats
tabu
actress casters
allergy gallery largely
Calculating time for 1000000 runs ...
22 seconds
Trả lời
C ++
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
containsthực hiện tìm kiếm từ trong word_groups. Sau đó, operator[]thực hiện tìm kiếm tương tự lần thứ hai.
Chúng tôi có thể thay thế những điều trên chỉ bằng:
word_groups[sorted_word].push_back(word);
( operator[]chèn một giá trị được tạo mặc định (tức là giá trị trống vector<std::string>) nếu nó không có trong bản đồ).
Chúng tôi không cần phải sao chép word_groupsbản đồ thành một vector để trả về nó get_groups(). Chúng tôi chỉ có thể trả lại bản đồ của chính nó.
Sau đó, trong hàm chính, chúng ta sẽ lặp lại nó với:
for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...
Chúng ta không cần phải lưu trữ chính chuỗi trong bản đồ, chúng ta có thể lưu chỉ mục của chuỗi trong vector đầu vào. (tức là map<string, vector<std::size_t>>).