Distância mínima entre duas palavras
A missão
Problema
Uma ferramenta de busca classifica um documento mais alto quando duas palavras da consulta aparecem perto uma da outra. Dada uma lista de palavras e duas palavras diferentes a e b, que aparecem pelo menos uma vez cada, retorne a menor distância entre uma posição que contém a e uma posição que contém b. A distância entre as posições i e j é o valor absoluto de i menos j.
Exemplos
Input: words = ["cat", "dog", "fox", "cat", "owl", "dog"], a = "cat", b = "dog"
Output: 1
Por quê: o cat na posição 0 e o dog na posição 1 são vizinhos
Input: words = ["red", "sky", "sky", "sky", "blue"], a = "blue", b = "red"
Output: 4
Por quê: cada palavra aparece uma vez, em pontas opostas
Input: words = ["up", "down"], a = "up", b = "down"
Output: 1
Por quê: edge case: é a menor lista capaz de conter as duas palavras
Dicas
0 / 3
Comparar cada posição de a com cada posição de b funciona, mas é quadrático quando as duas palavras são comuns.
Quando você chega a um a, o único b que pode dar a ele a melhor distância até agora é o b mais recente antes dele, e o mesmo vale no sentido contrário.
Varra a lista uma vez e lembre a última posição de a e a última posição de b. Cada vez que cair em uma das duas palavras e ambas já tiverem aparecido, compare a distância entre elas com a melhor até agora.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- a and b are different words
- a and b each appear at least once
Solução
Para um par de posições, a posterior é encontrada durante a varredura enquanto a anterior ainda está guardada, desde que nenhuma cópia da mesma palavra tenha aparecido entre elas. Se outra cópia apareceu no meio, essa cópia está mais perto da posição posterior, então o par ignorado nunca poderia ter sido o melhor. Verificar a distância só quando uma das duas palavras aparece mantém a passada barata. O tempo é O(n) e o espaço é 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")) # -> 1Travou na ideia, e não no código? Busca linear explica isso.