Las dos palabras más cercanas
La misión
Problema
Una herramienta de búsqueda posiciona mejor un documento cuando dos palabras de la consulta (query) aparecen cerca. Dada una lista de palabras y dos palabras distintas a y b que aparecen al menos una vez cada una, devuelve la menor distancia entre una posición que contenga a y una posición que contenga b. La distancia entre las posiciones i y j es el valor absoluto de i menos j.
Ejemplos
Input: words = ["cat", "dog", "fox", "cat", "owl", "dog"], a = "cat", b = "dog"
Output: 1
Por qué: el cat en 0 y el dog en 1 son vecinos
Input: words = ["red", "sky", "sky", "sky", "blue"], a = "blue", b = "red"
Output: 4
Por qué: cada palabra aparece una vez, en extremos opuestos
Input: words = ["up", "down"], a = "up", b = "down"
Output: 1
Por qué: caso límite: la lista más corta que puede contener ambas palabras
Pistas
0 / 3
Comparar cada posición de a con cada posición de b funciona, pero es cuadrático cuando ambas palabras son frecuentes.
Cuando llegas a una a, la única b que puede darle la mejor distancia hasta ahora es la b más reciente antes de ella, y lo mismo vale en sentido contrario.
Recorre la lista una vez y recuerda la última posición de a y la última posición de b. Cada vez que caes en cualquiera de las dos palabras y ya viste ambas, compara su distancia con la mejor hasta ahora.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- a and b are different words
- a and b each appear at least once
Solución
Para un par de posiciones, la posterior se encuentra durante el recorrido mientras la anterior sigue guardada, siempre que ninguna copia de la misma palabra haya aparecido entre ellas. Si otra copia sí apareció en medio, esa copia está más cerca de la posición posterior, así que el par omitido nunca pudo ser el mejor. Revisar la distancia solo cuando aparece una de las dos palabras mantiene la pasada barata. El tiempo es O(n) y el espacio es O(1).
def nearest_pair(words, a, b):
last_a = last_b = None # latest position of each word so far
best = len(words)
for i, w in enumerate(words):
if w == a:
last_a = i
elif w == b:
last_b = i
else:
continue # other words cannot change the answer
if last_a is not None and last_b is not None:
best = min(best, abs(last_a - last_b))
return best
print(nearest_pair(["cat", "dog", "fox", "cat", "owl", "dog"], "cat", "dog")) # -> 1
print(nearest_pair(["red", "sky", "sky", "sky", "blue"], "blue", "red")) # -> 4
print(nearest_pair(["up", "down"], "up", "down")) # -> 1¿Lo que te frena es la idea y no el código? Búsqueda lineal lo explica.