Prefijo común más largo
La misión
Problema
Dada una colección de palabras, encuentra la secuencia inicial de caracteres más larga con la que empiezan todas las palabras. La secuencia debe arrancar en el primer carácter de cada palabra, así que una coincidencia que aparece más adelante en una palabra no cuenta. Devuelve el texto vacío cuando las palabras no comparten ningún carácter inicial.
Ejemplos
Input: words = ["flower", "flow", "flight"]
Output: "fl"
Por qué: la tercera palabra rompe la coincidencia en el tercer carácter
Input: words = ["dog", "racecar"]
Output: ""
Por qué: las palabras no coinciden desde el principio
Input: words = []
Output: ""
Por qué: caso límite: no hay palabras que comparar
Pistas
0 / 3
Comparar las palabras entre sí por pares es más trabajo del necesario. La respuesta nunca puede ser más larga que cualquiera de las palabras, así que una sola palabra puede servir de referencia.
Alinea las palabras una debajo de otra y piensa en columnas en lugar de palabras. La respuesta termina en la primera columna donde dejan de coincidir.
Recorre los caracteres de la primera palabra por posición. En cada posición, comprueba que todas las demás palabras sean lo bastante largas y tengan ahí el mismo carácter. El primer fallo termina el prefijo en esa posición, y si se superan todas las posiciones, la primera palabra entera es el prefijo.
- Tiempo objetivo
- O(total characters)
- Espacio objetivo
- O(len(words) + len(words[0]))
Solución
La respuesta nunca puede superar a la primera palabra, así que esa palabra sirve de referencia y la búsqueda recorre sus posiciones. El recorrido columna por columna se detiene en la primera posición donde alguna palabra es demasiado corta o no coincide, que es justo donde termina el prefijo común. Comparar todas las palabras en cada columna, en lugar de palabra contra palabra, hace que el recorrido se detenga lo antes posible. El tiempo es O(total de caracteres) en el peor caso, y el espacio es O(1) además del slice devuelto.
def longest_shared_prefix(words):
if not words:
return ""
for i, ch in enumerate(words[0]): # walk the yardstick word column by column
for word in words[1:]:
if i >= len(word) or word[i] != ch:
return words[0][:i] # this column breaks the agreement
return words[0] # every column survived the check
print(longest_shared_prefix(["flower", "flow", "flight"])) # -> fl
print(longest_shared_prefix(["dog", "racecar"])) # ->
print(longest_shared_prefix([])) # ->¿Lo que te frena es la idea y no el código? Fundamentos de strings lo explica.