İçeriğe geç

Metindeki sözlük kelimelerini bul

Kolay#trie#prefix-pruning~15 dk

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

Hedef zaman
O(n · L + W)
Hedef alan
O(W + n · L)

Kısıtlar

  • the words are distinct

Kodda değil de fikirde mi takıldın? Trie ile Word Search bunu anlatıyor.

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