Metindeki sözlük kelimelerini bul
Görev tanımı
Problem
Bir text string'i ve birbirinden farklı words'ten oluşan bir liste verildiğinde, text'in i indeksinden j indeksine kadar, ikisi de dahil, diliminin kelimelerden biri olduğu her [i, j] çiftini döndür. Geçişler örtüşebilir. Çiftleri i'ye, sonra j'ye göre sıralı döndür.
Örnekler
Input: text = "bytesofcode", words = ["byte", "bytes", "code", "of", "so"]
Output: [[0, 3], [0, 4], [4, 5], [5, 6], [7, 10]]
Neden: byte, bytes, so, of ve code; so ile of o harfini paylaşıyor
Input: text = "ababa", words = ["aba", "ab"]
Output: [[0, 1], [0, 2], [2, 3], [2, 4]]
Input: text = "abc", words = ["d"]
Output: []
Neden: edge case: hiçbir kelime geçmiyor
İpuçları
0 / 3
Metnin her dilimini bir kelime kümesine karşı kontrol etmek işe yarar ama çoğu hiçbir kelimeyi başlatmayan O(n²) dilim kurar.
Sabit bir başlangıç indeksinden bir trie dilimi harf harf uzatmanı ve hiçbir kelime o harfle devam etmediği anda durmanı sağlar.
Her kelimeyi bir son işaretiyle bir trie'ye ekle. Her i başlangıcı için trie'yi text[i], text[i + 1] ve devamı boyunca dolaş, düğüm bir kelimenin sonunu işaretlediğinde [i, j] kaydet ve sonraki harfin çocuğu olmadığında dur.
- Hedef zaman
- O(n · L + W)
- Hedef alan
- O(W + n · L)
Kısıtlar
- the words are distinct
Çözüm
Trie her başlangıç konumunu, metin her kelimeden ayrıldığı anda duran bir dolaşmaya çevirir; trie güdümlü bir grid aramasını hızlı yapan budamanın (pruning) aynısı: bir kelime kümesi (set) yalnız bütün bir dilimin kelime olup olmadığını cevaplayabilir, bir trie ise dilimin hâlâ bir kelimeye dönüşüp dönüşemeyeceğini de cevaplar. i başlangıcından artan j ile dolaşmak o başlangıç için eşleşmeleri artan sırada bildirir, başlangıçlar da sırayla ziyaret edilir; bu yüzden çıktı sıralama gerektirmez. n uzunluğunda bir metin ve L uzunluğunda en uzun bir kelime için zaman O(n · L) artı W toplam harften trie'yi kurmak için O(W), alan O(W).
def word_positions(text, words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = True # a word ends here
found = []
for i in range(len(text)):
node = root
for j in range(i, len(text)):
node = node.get(text[j])
if node is None: # no word continues this way
break
if "$" in node:
found.append([i, j])
return found
print(word_positions("bytesofcode", ["byte", "bytes", "code", "of", "so"])) # -> [[0, 3], [0, 4], [4, 5], [5, 6], [7, 10]]
print(word_positions("ababa", ["aba", "ab"])) # -> [[0, 1], [0, 2], [2, 3], [2, 4]]
print(word_positions("abc", ["d"])) # -> []Kodda değil de fikirde mi takıldın? Trie ile Word Search bunu anlatıyor.