Préfixe commun le plus long (Leetcode)

Question

Lien ici J'apprends actuellement le c ++ provenant d'un arrière-plan python, donc je vais inclure une solution en python et en c ++ pour l'énoncé du problème ci-dessous, j'inclus les deux pour plus de commodité, si vous ne connaissez pas le c ++, n'hésitez pas pour revoir python et vice versa.

Ecrivez une fonction pour trouver la plus longue chaîne de préfixe commune parmi un tableau de chaînes. S'il n'y a pas de préfixe commun, renvoie une chaîne vide "".

Exemple 1:

Contribution: words = ['flower', 'flow', 'flight']

Production: 'fl'

Exemple 2:

Contribution: strs = ['dog', 'racecar', 'car']

Production: ''

longest_common_prefix.py

def get_longest(words):
    if not words:
        return ''
    common = words[0]
    for word in words:
        while not word.startswith(common):
            common = common[:-1]
    return common


if __name__ == '__main__':
    print(f"Longest prefix: \n{get_longest(['flower', 'flow', 'fly'])}")

Statistiques Leetcode:

• Durée d'exécution: 32 ms, plus rapide que 76,56% des soumissions en ligne Python3 pour le préfixe commun le plus long.

• Utilisation de la mémoire: 14 Mo, moins de 100,00% des soumissions en ligne Python3 pour le préfixe commun le plus long.

longest_common_prefix.h

#ifndef LEETCODE_LONGEST_COMMON_PREFIX_H
#define LEETCODE_LONGEST_COMMON_PREFIX_H

#include <string_view>
#include <vector>


std::string_view get_common_prefix(const std::vector<std::string_view>& words);


#endif //LEETCODE_LONGEST_COMMON_PREFIX_H

longest_common_prefix.cpp

#include <iostream>
#include <string_view>
#include <vector>


std::string_view get_common_prefix(const std::vector<std::string_view> &words) {
    if (words.empty())
        return "";
    std::string_view common = words[0];
    for (auto word: words) {
        while (word.find(common, 0) != 0) {
            common = common.substr(0, common.size() - 1);
        }
    }
    return common;
}


int main() {
    std::vector<std::string_view> xxx{"flow", "flower", "fly"};
    std::cout << "Longest prefix:\n" << get_common_prefix(xxx);
}

Statistiques Leetcode:

• Durée d'exécution: 0 ms, plus rapide que 100,00% des soumissions en ligne C ++ pour le préfixe commun le plus long.
• Utilisation de la mémoire: 9,9 Mo, moins de 7,29% des soumissions en ligne C ++ pour le préfixe commun le plus long.

Answer 1

Je vais seulement passer en revue le code C ++ ici, car tout ce que je pourrais suggérer pour le code Python s'applique également au C ++, donc est inclus dans cette revue.

Premièrement, l'interface est assez limitative - les entrées doivent être converties en vecteur d'objets de vue chaîne, ce qui n'est pas pratique si j'ai une liste chaînée de chaînes ou un flux d'entrée produisant des QStrings. Je recommande de changer pour accepter une paire d'itérateurs, ou en C ++ suffisamment moderne, un std::ranges::rangeobjet.

Ce test est inefficace:

word.find(common, 0) != 0

Si nous ne trouvons pas commonà la position 0, find()nous poursuivrons la recherche dans le reste de la chaîne (le code Python est meilleur ici). Nous avons besoin d'une implémentation de starts_with()(qui est en C ++ 20 std::string) - ou mieux, nous pourrions l'utiliser std::mismatch()pour trouver directement combien de chaînes sont communes, éliminant la boucle où nous supprimons à plusieurs reprises un seul caractère.

Voici ma tentative, également avec une simple optimisation pour revenir tôt lorsque la chaîne commune devient vide:

#include <algorithm>
#include <iterator>
#include <string_view>
#include <vector>

namespace
{
    template<typename String>
    String common_prefix(const String& a, const String& b)
    {
        using std::begin;
        using std::end;
        auto end_iter = std::mismatch(begin(a), end(a), begin(b), end(b));
        if (end_iter.first == end(a)) { return a; }
        if (end_iter.second == end(b)) { return b; }
        return String(begin(a), end_iter.first - begin(a));
    }
}

template<typename Iter, typename IterEnd = Iter>
std::string_view get_common_prefix(Iter first, IterEnd last)
{
    if (first==last) { return ""; }
    std::string_view common = *first;
    for (auto it = first;  it != last;  ++it) {
        common = common_prefix(common, *it);
        if (common.empty()) { return common; }
    }
    return common;
}

template<typename Container>
std::string_view get_common_prefix(const Container& words)
{
    using std::begin;
    using std::end;
    return get_common_prefix(begin(words), end(words));
}