Saltar al contenido

Las dos palabras más cercanas

Fácil#single-pass#linear-scan~15 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(1)

Restricciones

  • a and b are different words
  • a and b each appear at least once

¿Lo que te frena es la idea y no el código? Búsqueda lineal lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio