Implement Trie (Prefix Tree)

Q: Mengapa menggunakan trie alih-alih hash set?

Hash set menemukan kata utuh dalam O(L) , tetapi tidak dapat menjawab pertanyaan tentang prefiks tanpa memindai setiap kata. Menyimpan setiap prefiks dalam set kedua membutuhkan 210 huruf untuk satu kata sepanjang 20 huruf. Trie menyimpan setiap prefiks yang sama satu kali dan menjawab kedua pertanyaan dengan satu penelusuran.

SedangTrie

+10

Buat trie (pohon prefiks) untuk kata-kata berhuruf kecil dengan tiga operasi: insert w menambahkan kata w, search w memberi tahu apakah w sendiri telah ditambahkan, dan startsWith p memberi tahu apakah ada kata yang telah ditambahkan dan diawali dengan p. Sebuah kata dianggap sebagai prefiks dari dirinya sendiri.

Operasi i adalah ops[i] pada words[i]. Jalankan operasi-operasi tersebut secara berurutan pada trie kosong dan kembalikan satu string untuk setiap operasi: "null" untuk insert, "true" atau "false" untuk search atau startsWith.

Fungsi

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: operasi-operasi, sesuai urutan pelaksanaannya
wordsstring-array: kata atau awalan untuk setiap operasi
Mengembalikanstring-array: satu jawaban per operasi, sebagai teks

Batasan

1 ≤ ops.length ≤ 2000
words.length == ops.length
Setiap ops[i] adalah insert, search, atau startsWith.
1 ≤ words[i].length ≤ 20
words[i] hanya berisi huruf kecil dalam bahasa Inggris.

Contoh

Input: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Output: ["null", "false", "true", "null", "true"]
Penjelasan: car merupakan awalan dari card, jadi startsWith car bernilai "true", tetapi car belum pernah disisipkan, jadi pencarian pertama menghasilkan "false". Setelah insert car, pencarian menemukannya.

Input: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Output: ["null", "null", "true", "false", "false", "true", "true"]
Penjelasan: Kedua kata dimulai dengan te, tetapi tidak ada yang persis sama dengan te, jadi startsWith bernilai "true" dan pencarian bernilai "false". Tidak ada kata yang dimulai dengan tex, dan tea adalah prefiks dari dirinya sendiri.

Input: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Output: ["false", "false", "null", "true", "false", "true"]
Penjelasan: Pada trie kosong, kedua kueri bernilai "false". Setelah insert dog, pencarian menemukannya, tidak ada kata yang diawali dengan dogs, dan do merupakan awalan dari dog.

Pertanyaan lanjutan

Bagaimana cara menambahkan operasi countPrefix p yang mengembalikan jumlah kata tersimpan yang berbeda dan diawali dengan p, tetap dalam waktu O(L)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Hash set dapat menjawab search, tetapi tidak mengenal konsep awalan, sehingga startsWith akan memindai setiap kata. Trie menyimpan setiap kata sebagai jalur huruf dari akar: kata-kata dengan awalan yang sama berbagi jalur, dan sebuah penanda menunjukkan tempat kata yang disimpan berakhir. Kedua kueri hanya memerlukan satu penelusuran dengan paling banyak L tautan.

Simpan daftar kata dan pindai

Intuisi

Simpan setiap kata yang dimasukkan dalam sebuah list. search w membandingkan w dengan setiap kata yang tersimpan, dan startsWith p memeriksa apakah ada kata tersimpan yang diawali dengan p. Cara ini benar karena menguji definisinya secara langsung. Dengan n kata tersimpan, setiap kueri memerlukan hingga n perbandingan yang masing-masing membandingkan hingga L huruf: 1,000 kata dan 1,000 kueri menghasilkan satu juta perbandingan string.

Algoritma

Mulai dengan list kosong.
insert w: tambahkan w di akhir.
search w: kembalikan apakah ada kata tersimpan yang sama dengan w.
startsWith p: kembalikan apakah ada kata tersimpan yang diawali dengan p.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

Sebuah trie: tautan anak dan penanda akhir

Intuisi

Setiap simpul mewakili satu prefiks, yaitu huruf-huruf pada jalur dari akar ke simpul tersebut. Simpul ini memiliki tautan anak untuk setiap huruf yang mungkin muncul berikutnya (26 slot atau sebuah map) dan sebuah penanda isEnd yang menunjukkan apakah sebuah kata tersimpan berakhir tepat di sana. Menyisipkan tea membuat simpul untuk t, te, dan tea; lalu menyisipkan ten hanya menambahkan ten, karena kedua kata berbagi jalur untuk te.

Penelusuran yang menemukan tautan yang hilang membuktikan bahwa tidak ada kata tersimpan yang diawali huruf-huruf tersebut: tex berhenti di te, yang tidak memiliki tautan x. Penelusuran yang mencapai akhir berada di simpul untuk kueri tersebut, sehingga startsWith bernilai true dan search memberikan jawaban berdasarkan penandanya. Simpul untuk te ada, tetapi penandanya tidak aktif, sehingga search te bernilai false. Setiap operasi mengikuti paling banyak L tautan, berapa pun jumlah kata yang tersimpan, dan trie memiliki satu simpul untuk setiap prefiks yang berbeda.

Algoritma

Buat root tanpa link anak dan isEnd dalam keadaan mati.
insert w: dari root, ikuti link untuk setiap huruf, buat node jika belum ada. Atur isEnd ke aktif pada node terakhir.
find(p): dari root, ikuti link untuk setiap huruf; kembalikan nothing segera jika salah satunya tidak ada, jika tidak, kembalikan node yang dicapai.
search w: bernilai true jika find(w) mengembalikan node dengan isEnd yang aktif.
startsWith p: bernilai true jika find(p) mengembalikan sebuah node.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Jebakan dan kasus tepi

Membiarkan search menjawab true setiap kali jalurnya ada. Setelah insert card, jalur untuk car ada, tetapi search car harus menjawab false.
Mengatur isEnd hanya pada node yang baru dibuat. Menyisipkan card setelah cards tidak membuat apa pun, tetapi node terakhir perlu memiliki flag-nya.
Membuat child baru saat tautannya sudah ada. Menyisipkan ten dengan node t baru akan menghilangkan tea.
Membaca melewati akhir jalur. startsWith sunny saat hanya sun yang tersimpan harus berhenti pada tautan pertama yang tidak ada dan menjawab false.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu sebuah trie?

Penyisipan, pencarian, dan startsWith masing-masing mengikuti satu tautan untuk setiap huruf, sehingga masing-masing membutuhkan O(L) untuk kata dengan panjang L, berapa pun jumlah kata yang disimpan. Ruang yang dibutuhkan adalah O(T) node untuk total T huruf yang disisipkan, dengan setiap node menyimpan hingga 26 tautan anak.

Mengapa menggunakan trie alih-alih hash set?

Hash set menemukan kata utuh dalam O(L), tetapi tidak dapat menjawab pertanyaan tentang prefiks tanpa memindai setiap kata. Menyimpan setiap prefiks dalam set kedua membutuhkan 210 huruf untuk satu kata sepanjang 20 huruf. Trie menyimpan setiap prefiks yang sama satu kali dan menjawab kedua pertanyaan dengan satu penelusuran.

Apakah node trie sebaiknya menggunakan array berisi 26 tautan atau hash map?

array menemukan anak dengan satu indeks, tetapi membutuhkan 26 slot per node, bahkan untuk node dengan satu anak. Map hanya menyimpan anak yang ada dan berfungsi untuk alfabet apa pun, dengan biaya hash per huruf. Untuk bahasa Inggris huruf kecil, keduanya bisa digunakan; untuk Unicode atau trie yang jarang, map menghemat memori.

def trieOps(ops, words):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Output yang diharapkan

["null", "false", "true", "null", "true"]