En yakın iki kelime
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
a'nın her konumunu b'nin her konumuyla karşılaştırmak işe yarar, ama iki kelime de yaygın olduğunda karesel.
Bir a'ya vardığında, ona şimdiye kadarki en iyi mesafeyi verebilecek tek b ondan önceki en son b'dir; tersi için de aynısı geçerli.
Bir kez tara ve a'nın en son konumunu ve b'nin en son konumunu hatırla. İki kelimeden birine her denk geldiğinde ve ikisi de görülmüşse aralarındaki mesafeyi şimdiye kadarki en iyiyle karşılaştır.
- 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
Çözüm
Bir konum çifti için, aralarına aynı kelimenin başka bir kopyası girmediği sürece, sonraki konuma tarama sırasında önceki hâlâ saklıyken ulaşılır. Aralarına başka bir kopya girdiyse o kopya sonraki konuma daha yakındır; yani atlanan çift asla en iyisi olamazdı. Mesafeyi yalnız iki kelimeden biri görüldüğünde kontrol etmek geçişi ucuz tutar. Zaman O(n), alan 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")) # -> 1Kodda değil de fikirde mi takıldın? Doğrusal arama bunu anlatıyor.