Anagram grup Leetcode

Question

Tautkan di sini

Saya akan menyertakan solusi dengan Python dan C ++ dan Anda dapat memeriksanya. Saya sangat tertarik untuk meninjau kode C ++ yang merupakan hal yang baru saya pelajari; mereka yang tidak tahu C ++ dapat meninjau kode Python. Kedua solusi memiliki logika yang serupa, jadi peninjauan akan berlaku untuk solusi apa pun.

---

Pernyataan masalah

Diberikan sebuah array string strings, kelompokkan anagram bersama-sama. Anda dapat mengembalikan jawabannya dalam urutan apa pun. Anagram adalah kata atau frasa yang dibentuk dengan mengatur ulang huruf dari kata atau frasa yang berbeda, biasanya menggunakan semua huruf asli tepat satu kali.

Contoh:

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

Kedua solusi melibatkan pembuatan pemetaan dari karakter kata yang diurutkan menurut abjad ke kata yang sesuai dan setiap kata yang ditemukan yang cocok, akan ditambahkan ke grup yang sesuai. Dan karena disarankan sebelumnya di posting saya sebelumnya untuk tidak bergantung pada statistik leetcode karena mereka tidak akurat, saya menghitung waktu baik solusi c ++ dan python untuk 1.000.000 berjalan pada kumpulan kata yang sama untuk melihat apa yang muncul. Anehnya, solusi python mengungguli solusi c ++ hampir 2x. Waktu yang dihasilkan ~ = 10, 20 detik untuk python dan c ++ masing-masing saat dijalankan pada i5 2,7 GHZ mbp saya. Mengingat kedua penerapannya hampir serupa, bukankah c ++ harus 10x kali lebih cepat daripada 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)

Hasil:

[['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";
}

Hasil:

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};
    }

containsmelakukan pencarian kata dalam word_groups. Kemudian operator[]lakukan pencarian yang sama untuk kedua kalinya.

Kita bisa mengganti yang di atas hanya dengan:

    word_groups[sorted_word].push_back(word);

( operator[]menyisipkan nilai bawaan yang dibangun (yaitu kosong vector<std::string>) jika tidak ada di peta).

---

Kita tidak perlu menyalin word_groupspeta menjadi vektor untuk mengembalikannya get_groups(). Kami hanya dapat mengembalikan peta itu sendiri.

Kemudian di fungsi utama kami mengulanginya dengan:

for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
    for (const auto &word: group.second)
        ...

---

Kita tidak perlu menyimpan string itu sendiri di peta, kita bisa menyimpan indeks string di vektor input. (yaitu map<string, vector<std::size_t>>).