İçeriğe geç

En yakın iki kelime

Kolay#single-pass#linear-scan~15 dk

Görev tanımı

Problem

Bir arama aracı, iki sorgu kelimesi birbirine yakın göründüğünde bir belgeyi daha üst sıraya koyuyor. Bir kelime listesi ve her biri en az bir kez geçen iki farklı a ve b kelimesi verildiğinde, a'yı tutan bir konum ile b'yi tutan bir konum arasındaki en küçük mesafeyi döndür. i ve j konumları arasındaki mesafe, i eksi j'nin mutlak değeridir.

Örnekler

Input:  words = ["cat", "dog", "fox", "cat", "owl", "dog"], a = "cat", b = "dog"
Output: 1
Neden: 0'daki cat ile 1'deki dog komşu
Input:  words = ["red", "sky", "sky", "sky", "blue"], a = "blue", b = "red"
Output: 4
Neden: her kelime bir kez, zıt uçlarda geçiyor
Input:  words = ["up", "down"], a = "up", b = "down"
Output: 1
Neden: edge case: iki kelimeyi tutabilen en kısa liste

İpuçları

0 / 3

Hedef zaman
O(n)
Hedef alan
O(1)

Kısıtlar

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

Kodda değil de fikirde mi takıldın? Doğrusal arama bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case