Prefixo comum mais longo (Leetcode)

Question

Link aqui Estou atualmente aprendendo c ++ vindo de um plano de fundo de python, então incluirei uma solução em python e em c ++ para a declaração do problema abaixo, estou incluindo ambos por conveniência, se você não conhece c ++, fique à vontade para revisar o python e vice-versa.

Escreva uma função para encontrar a string de prefixo comum mais longa entre uma matriz de strings. Se não houver um prefixo comum, retorne uma string vazia "".

Exemplo 1:

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

Resultado: 'fl'

Exemplo 2:

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

Resultado: ''

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

Estatísticas Leetcode:

• Tempo de execução: 32 ms, mais rápido que 76,56% dos envios online do Python3 para o prefixo comum mais longo.

• Uso de memória: 14 MB, menos de 100,00% dos envios online do Python3 para o prefixo comum mais longo.

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

Estatísticas Leetcode:

• Tempo de execução: 0 ms, mais rápido do que 100,00% dos envios on-line C ++ para o prefixo comum mais longo.
• Uso de memória: 9,9 MB, menos de 7,29% dos envios on-line C ++ para o prefixo comum mais longo.

Answer 1

Vou apenas revisar o código C ++ aqui, pois tudo que eu poderia sugerir para o código Python também se aplica ao C ++, portanto, está incluído nesta revisão.

Em primeiro lugar, a interface é bastante limitante - as entradas precisam ser convertidas em vetor de objetos de visualização de string, o que é inconveniente se eu tiver uma lista vinculada de strings ou um fluxo de entrada que produza QStrings. Eu recomendo mudar para aceitar um par de iteradores, ou em C ++ suficientemente moderno, um std::ranges::rangeobjeto.

Este teste é ineficiente:

word.find(common, 0) != 0

Se não encontrarmos commonna posição 0, find()continuará pesquisando o resto da string (o código Python é melhor aqui). Precisamos de uma implementação de starts_with()(que está em C ++ 20's std::string) - ou melhor, poderíamos usar std::mismatch()para descobrir diretamente quanto das strings são comuns, eliminando o loop em que removemos repetidamente um único caractere.

Aqui está minha tentativa de fazer isso, também com uma otimização simples para retornar mais cedo quando a string comum ficar vazia:

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