Longest Common Prefix

Q: ¿Cuál es la complejidad temporal del prefijo común más largo?

Ambos recorridos se ejecutan en tiempo O(S) , donde S es el número total de letras, con memoria adicional O(1) , aparte de la respuesta. El recorrido por columnas también está acotado por n × (L+1) para una respuesta de longitud L , por lo que se detiene pronto cuando las palabras no coinciden cerca del inicio.

Q: ¿Qué debería devolver Longest Common Prefix cuando no hay ningún prefijo común?

La cadena vacía "" . Eso ocurre en cuanto dos palabras empiezan con letras diferentes, como en stack , queue y heap .

Q: ¿Qué es mejor, el escaneo horizontal o el vertical?

Ambos tienen el mismo peor caso, O(S) . El escaneo vertical es la opción más segura: se detiene en la primera columna en la que alguna palabra no coincide, mientras que el escaneo horizontal puede comparar un prefijo largo con muchas palabras antes de que una palabra posterior lo acorte.

FácilArrays y cadenas

+10

Recibes un arreglo de palabras strs. Devuelve la cadena más larga con la que comienzan todas las palabras. Si no todas las palabras empiezan con la misma letra, devuelve la cadena vacía "". Una palabra cuenta como prefijo de sí misma, así que una sola palabra es su propia respuesta.

Función

longestCommonPrefix(strs: string-array) → string

strsstring-array: las palabras que se van a comparar
Devuelvestring: el prefijo más largo que comparten todas las palabras, o una cadena vacía

Restricciones

1 ≤ strs.length ≤ 200
1 ≤ strs[i].length ≤ 200
Cada palabra contiene solo letras minúsculas del inglés.

Ejemplos

Entrada: strs = ["interview", "internet", "interval", "internal"]
Salida: "inter"
Explicación: Las cuatro palabras comienzan con inter. En la siguiente posición, interview y interval tienen una v, y internet e internal una n, así que el prefijo termina ahí.

Entrada: strs = ["stack", "queue", "heap"]
Salida: ""
Explicación: Las palabras empiezan con s, q y h. No coinciden en la primera letra, así que la respuesta está vacía.

Entrada: strs = ["prefix", "pre", "prepare"]
Salida: "pre"
Explicación: pre es la palabra más corta y las otras dos comienzan con ella, así que es toda la respuesta. Un prefijo compartido nunca puede ser más largo que la palabra más corta.

Para ir más allá

Supón que la lista permanece fija y llegan muchas palabras de consulta. ¿Cómo encontrarías el prefijo más largo de cada consulta que comparte con alguna palabra de la lista, sin volver a recorrer la lista?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Una letra pertenece a la respuesta solo si todas las palabras la tienen en la misma posición, y la respuesta termina en la primera posición en la que una palabra no coincide o se queda sin letras. Ambos enfoques leen las palabras letra por letra en un orden distinto. El recorrido por columnas se detiene en el primer desacuerdo.

Acorta el prefijo palabra por palabra

Intuición

Supón que la primera palabra completa es la respuesta. Redúcela a la parte que comparte con la segunda palabra, luego con la tercera, y así sucesivamente. El prefijo común de muchas palabras es el prefijo común de las dos primeras, luego de ese prefijo y la tercera palabra: cada paso solo puede conservarlo o acortarlo. Por ejemplo, en el ejemplo 1, el candidato pasa de interview a inter después de la segunda palabra y se queda ahí.

Cada letra se compara como máximo una vez, así que el tiempo es O(S) para S letras en total. El punto débil es el orden: con 200 palabras de 200 letras en las que solo la última palabra difiere en su primera letra, haces cerca de 40,000 comparaciones antes de que la última palabra reduzca el prefijo a nada.

Algoritmo

Establece prefixLen en la longitud de strs[0].
Para cada una de las demás palabras, cuenta cuántas letras iniciales comparte con strs[0], hasta prefixLen.
Establece prefixLen en ese número y detente antes si llega a 0.
Devuelve las primeras prefixLen letras de strs[0].

def longestCommonPrefix(strs):
    first = strs[0]
    prefix_len = len(first)
    for word in strs[1:]:
        common = 0
        while common < prefix_len and common < len(word) and word[common] == first[common]:
            common += 1
        prefix_len = common
        if prefix_len == 0:
            break
    return first[:prefix_len]

Compara columna por columna

Intuición

Lee las palabras como una tabla, una columna a la vez. Toma la letra de strs[0] en la columna actual y comprueba que todas las demás palabras tengan la misma letra allí. La primera vez que una palabra no coincida, o sea demasiado corta para tener esa columna, la respuesta es strs[0] hasta esa columna.

La respuesta es exactamente la secuencia de columnas en las que todas las palabras coinciden, y este bucle recorre esa secuencia desde la izquierda y se detiene donde deja de cumplirse. Si nada la interrumpe, strs[0] es la respuesta.

Con n palabras y una respuesta de longitud L, el bucle hace como máximo n × (L+1) comprobaciones, lo que también es O(S). En el caso en que solo la última de 200 palabras difiera en su primera letra, se detiene después de 199 comparaciones.

Algoritmo

Sea first strs[0].
Para cada columna col desde 0 hasta la longitud de first menos uno, lee first[col].
Para cada una de las otras palabras, si no tiene una letra en col o su letra es diferente, devuelve las primeras col letras de first.
Si todas las columnas coinciden, devuelve first.

def longestCommonPrefix(strs):
    first = strs[0]
    for col in range(len(first)):
        for word in strs[1:]:
            if col == len(word) or word[col] != first[col]:
                return first[:col]
    return first

Errores comunes y casos límite

Leer más allá del final de una palabra más corta. En prefix, pre, prepare, la columna 3 existe en prefix, pero no en pre; comprueba la longitud antes de leer la letra.
Comparar solo la primera y la última palabra sin ordenar. En abc, xbd, abd, esas dos comparten ab, pero xbd rompe la columna 0 y la respuesta está vacía.
Devolver null o un marcador de posición cuando no hay nada en común. La respuesta es la cadena vacía.
Olvidar que una sola palabra es su propio prefijo: algorithm por sí sola devuelve algorithm.
Añadir una letra a la vez a una cadena inmutable. Una respuesta de 200 letras implica 200 copias; conserva la longitud y recorta la primera palabra una sola vez.

Preguntas frecuentes4

¿Cuál es la complejidad temporal del prefijo común más largo?

Ambos recorridos se ejecutan en tiempo O(S), donde S es el número total de letras, con memoria adicional O(1), aparte de la respuesta. El recorrido por columnas también está acotado por n × (L+1) para una respuesta de longitud L, por lo que se detiene pronto cuando las palabras no coinciden cerca del inicio.

¿Puedes encontrar el prefijo común más largo ordenando las palabras?

Sí. En orden alfabético, todas las palabras entre la primera y la última empiezan con lo que comparten esas dos, así que comparar solo esas dos da la respuesta. La ordenación compara alrededor de n log n pares de palabras, lo que cuesta más que un solo recorrido, pero el código es breve.

¿Qué debería devolver Longest Common Prefix cuando no hay ningún prefijo común?

La cadena vacía "". Eso ocurre en cuanto dos palabras empiezan con letras diferentes, como en stack, queue y heap.

¿Qué es mejor, el escaneo horizontal o el vertical?

Ambos tienen el mismo peor caso, O(S). El escaneo vertical es la opción más segura: se detiene en la primera columna en la que alguna palabra no coincide, mientras que el escaneo horizontal puede comparar un prefijo largo con muchas palabras antes de que una palabra posterior lo acorte.

def longestCommonPrefix(strs):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

strs = ["interview", "internet", "interval", "internal"]

Salida Esperada

"inter"