Längstes gemeinsames Präfix (Leetcode)

Question

Link hier Ich lerne gerade C ++ aus einem Python-Hintergrund, daher werde ich eine Lösung in Python und in C ++ für die unten stehende Problemstellung einfügen. Ich beziehe beide der Einfachheit halber ein. Wenn Sie C ++ nicht kennen, fühlen Sie sich frei Python zu überprüfen und umgekehrt.

Schreiben Sie eine Funktion, um die längste gemeinsame Präfixzeichenfolge unter einem Array von Zeichenfolgen zu finden. Wenn es kein gemeinsames Präfix gibt, geben Sie eine leere Zeichenfolge "" zurück.

Beispiel 1:

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

Ausgabe: 'fl'

Beispiel 2:

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

Ausgabe: ''

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'])}")

Leetcode-Statistiken:

• Laufzeit: 32 ms, schneller als 76,56% der Python3-Online-Einreichungen für das längste gemeinsame Präfix.

• Speichernutzung: 14 MB, weniger als 100,00% der Python3-Online-Einreichungen für das längste gemeinsame Präfix.

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

Leetcode-Statistiken:

• Laufzeit: 0 ms, schneller als 100,00% der C ++ - Online-Einreichungen für das längste gemeinsame Präfix.
• Speichernutzung: 9,9 MB, weniger als 7,29% der C ++ - Online-Einreichungen für das längste gemeinsame Präfix.

Answer 1

Ich werde hier nur den C ++ - Code überprüfen, da alles, was ich für den Python-Code vorschlagen könnte, auch für C ++ gilt und daher in dieser Überprüfung enthalten ist.

Erstens ist die Schnittstelle ziemlich einschränkend - die Eingaben müssen in einen Vektor von Objekten mit Zeichenfolgenansicht konvertiert werden, was unpraktisch ist, wenn ich eine verknüpfte Liste von Zeichenfolgen oder einen Eingabestream habe, der QStrings ergibt . Ich empfehle, ein std::ranges::rangeObjekt zu ändern, um ein Paar Iteratoren zu akzeptieren, oder in ausreichend modernem C ++ ein Objekt.

Dieser Test ist ineffizient:

word.find(common, 0) != 0

Wenn wir commonan Position 0 nicht finden , find()wird der Rest der Zeichenfolge weiter durchsucht (der Python-Code ist hier besser). Wir brauchen eine Implementierung von starts_with()(in C ++ 20 std::string) - oder besser, wir könnten std::mismatch()direkt herausfinden, wie viele Zeichenfolgen gemeinsam sind, und die Schleife eliminieren, in der wir wiederholt ein einzelnes Zeichen entfernen.

Hier ist mein Versuch, auch mit einer einfachen Optimierung, früh zurückzukehren, wenn die gemeinsame Zeichenfolge leer wird:

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