Prefijo común más largo (Leetcode)

Question

Enlace aquí Actualmente estoy aprendiendo c ++ proveniente de un fondo de Python, así que incluiré una solución en Python y en C ++ para la declaración del problema a continuación, incluyo ambos por conveniencia, si no conoce C ++, no dude para revisar Python y viceversa.

Escriba una función para encontrar la cadena de prefijo común más larga entre una matriz de cadenas. Si no hay un prefijo común, devuelve una cadena vacía "".

Ejemplo 1:

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

Salida: 'fl'

Ejemplo 2:

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

Salida: ''

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

Estadísticas de Leetcode:

• Tiempo de ejecución: 32 ms, más rápido que el 76,56% de los envíos en línea de Python3 para el prefijo común más largo.

• Uso de memoria: 14 MB, menos del 100,00% de los envíos en línea de Python3 para el prefijo común más largo.

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

Estadísticas de Leetcode:

• Tiempo de ejecución: 0 ms, más rápido que el 100,00% de los envíos en línea de C ++ para el prefijo común más largo.
• Uso de memoria: 9,9 MB, menos del 7,29% de los envíos en línea de C ++ para el prefijo común más largo.

Answer 1

Solo voy a revisar el código C ++ aquí, ya que todo lo que podría sugerir para el código Python también se aplica a C ++, por lo que se incluye en esta revisión.

En primer lugar, la interfaz es bastante limitante: las entradas deben convertirse en un vector de objetos de vista de cadena, lo cual es inconveniente si tengo una lista vinculada de cadenas o un flujo de entrada que produce QStrings. Recomiendo cambiar para aceptar un par de iteradores, o en C ++ suficientemente moderno, un std::ranges::rangeobjeto.

Esta prueba es ineficiente:

word.find(common, 0) != 0

Si no encontramos commonen la posición 0, find()continuaremos buscando el resto de la cadena (el código Python es mejor aquí). Necesitamos una implementación de starts_with()(que está en C ++ 20's std::string) - o mejor, podríamos usar std::mismatch()para encontrar directamente cuántas de las cadenas son comunes, eliminando el bucle donde repetidamente eliminamos un solo carácter.

Aquí está mi intento de hacerlo, también con una simple optimización para regresar temprano cuando la cadena común se vacía:

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