Leetcode组字谜

Question

链接在这里

我将在PythonandC++中包含一个解决方案，您可以查看其中一个。我最感兴趣的是回顾C++代码，这是我最近开始学习的一件事；那些不知道C++的人可以查看C++代码。这两种解决方案都有相似的逻辑，因此审查将适用于任何方案。

问题陈述

给定字符串strs数组，将字谜组合在一起。你可以按任何顺序返回答案。Anagram是通过重新排列不同单词或短语的字母而形成的单词或短语，通常只使用所有原始字母一次。

示例：

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

这两种解决方案都涉及创建一个从单词字符按字母顺序排列到相应单词的映射，并将遇到的每个匹配单词添加到相应的组中。而且，由于前面的文章建议不要依赖leetcode的统计数据，因为它们是不准确的，所以我给c++和python解决方案都计时了1,000,000次运行在同一组单词上，看看会发生什么。令人惊讶的是，python解决方案的性能几乎比c++解决方案高出2倍。在我的~= 2.7GHzMBP上分别运行python和c++的时间分别为i5 10、20秒和20秒。考虑到这两种实现几乎是相似的，难道c++不应该比python快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

Answer 1

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>>)。