Prefisso comune più lungo (Leetcode)

Question

Link qui Attualmente sto imparando c ++ proveniente da uno sfondo di python, quindi includerò una soluzione in python e in c ++ per la dichiarazione del problema di seguito, li includo entrambi per comodità, se non conosci c ++, sentiti libero per rivedere python e viceversa.

Scrivi una funzione per trovare la stringa di prefisso comune più lunga tra un array di stringhe. Se non esiste un prefisso comune, restituisce una stringa vuota "".

Esempio 1:

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

Produzione: 'fl'

Esempio 2:

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

Produzione: ''

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

Statistiche Leetcode:

• Runtime: 32 ms, più veloce del 76,56% degli invii online di Python3 per il prefisso comune più lungo.

• Utilizzo della memoria: 14 MB, meno del 100,00% degli invii online di Python3 per il prefisso comune più lungo.

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

Statistiche Leetcode:

• Runtime: 0 ms, più veloce del 100,00% degli invii in linea C ++ per il prefisso comune più lungo.
• Utilizzo della memoria: 9,9 MB, meno del 7,29% degli invii in linea C ++ per il prefisso comune più lungo.

Answer 1

Esaminerò solo il codice C ++ qui, poiché tutto ciò che potrei suggerire per il codice Python si applica anche al C ++, quindi è incluso in questa recensione.

In primo luogo, l'interfaccia è piuttosto limitante: gli input devono essere convertiti in vettori di oggetti di visualizzazione stringa, il che è scomodo se ho un elenco collegato di stringhe o un flusso di input che produce QStrings. Consiglio di cambiare per accettare un paio di iteratori, o in C ++ sufficientemente moderno, un std::ranges::rangeoggetto.

Questo test è inefficiente:

word.find(common, 0) != 0

Se non troviamo commonalla posizione 0, find()continueremo a cercare il resto della stringa (il codice Python è migliore qui). Abbiamo bisogno di un'implementazione di starts_with()(che è in C ++ 20 std::string) - o meglio, potremmo usare std::mismatch()per trovare direttamente la quantità di stringhe comuni, eliminando il ciclo in cui rimuoviamo ripetutamente un singolo carattere.

Ecco il mio tentativo in tal senso, anche con una semplice ottimizzazione per tornare presto quando la stringa comune diventa vuota:

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