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 en todas las palabras, y solo necesitan O(1) de memoria adicional, aparte de la respuesta. El recorrido por columnas también está limitado por n × (L+1) , donde L es la longitud de la respuesta, así que se detiene antes si las palabras no coinciden cerca del principio.

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

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

Q: ¿Cuál es mejor, el escaneo horizontal o el vertical?

Ambos tienen el mismo caso peor, O(S) . El escaneo vertical, columna por columna, 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 tardía lo acorte.

FácilArrays y cadenas

+10

Recibes un arreglo de palabras strs. Devuelve la cadena más larga con la que empiezan todas las palabras. Si no todas las palabras comienzan 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 para 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 únicamente letras minúsculas del alfabeto 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, mientras que internet e internal tienen 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 no comparten ningún prefijo y 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 esa es la respuesta completa. Un prefijo común nunca puede ser más largo que la palabra más corta.

+19 pruebas ocultas al enviar

Para ir más allá

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

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 tienen esa misma letra en la misma posición, y la respuesta termina en la primera posición en la que alguna palabra no coincide o se queda sin letras. Ambos enfoques de abajo leen las palabras letra por letra; se diferencian en el orden en que las leen. El recorrido por columnas se detiene ante la primera discrepancia, por lo que nunca lee más allá de la respuesta más una columna.

Reduce el prefijo palabra por palabra

Intuición

Empieza suponiendo que la primera palabra completa es la respuesta. Después, compárala con la segunda palabra letra por letra y redúcela a la parte que comparten. Compara lo que queda con la tercera palabra, y así sucesivamente. Después de la última palabra, lo que queda es común a todas.

Esto es correcto porque el prefijo común de muchas palabras es el prefijo común de las dos primeras, después el de ese resultado y la tercera palabra, y así sucesivamente: cada paso solo puede mantenerlo o acortarlo. Para interview, internet, interval, internal, 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), donde S es el número total de letras. Solo conservas una longitud, no una copia. El punto débil es el orden: con 200 palabras de 200 letras, donde las primeras 199 coinciden y solo la última difiere en su primera letra, comparas las 200 letras con cada una de las primeras 199 palabras, cerca de 40.000 comparaciones, antes de que la última palabra reduzca el prefijo a nada.

Algoritmo

Establece prefixLen con 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 con ese recuento 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. La columna 0 contiene la primera letra de cada palabra, la columna 1 la segunda, y así sucesivamente. 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 esas columnas de izquierda a derecha y se detiene en la primera que interrumpe la secuencia. Si ninguna columna la interrumpe, strs[0] es la respuesta; entonces es la palabra más corta o tiene la misma longitud que esta.

El bucle lee como máximo una columna más allá de la respuesta, así que con n palabras y una respuesta de longitud L, realiza como máximo n × (L+1) comprobaciones, y nunca lee la misma letra de una palabra dos veces, por lo que también es O(S). En el caso anterior, en el que 199 palabras coinciden y la última difiere en su primera letra, se detiene después de la primera columna: 199 comparaciones en lugar de casi 40.000.

Algoritmo

Sea first igual a 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 distinta, 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

La respuesta es breve y los errores están al final.

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 en el orden dado. Ese atajo requiere ordenar primero las palabras: en abc, xbd, abd, la primera y la última comparten ab, pero xbd no coincide en la columna 0 y la respuesta es una cadena 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.
Construir la respuesta añadiendo una letra cada vez a una cadena inmutable. Para una respuesta de 200 letras, eso supone 200 copias; lleva la cuenta de la longitud y extrae el comienzo de la primera palabra una sola vez, al final.

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 en todas las palabras, y solo necesitan O(1) de memoria adicional, aparte de la respuesta. El recorrido por columnas también está limitado por n × (L+1), donde L es la longitud de la respuesta, así que se detiene antes si las palabras no coinciden cerca del principio.

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

Sí. En orden alfabético, cada palabra que queda entre la primera y la última empieza con lo que comparten esas dos, así que comparar solo la primera y la última palabra 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 corto.

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

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

¿Cuál es mejor, el escaneo horizontal o el vertical?

Ambos tienen el mismo caso peor, O(S). El escaneo vertical, columna por columna, 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 tardía lo acorte.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

"inter"