Pular para o conteúdo

Distância mínima entre duas palavras

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

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

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

Travou na ideia, e não no código? Busca linear explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado