Design Add and Search Words Data Structure
Buat dictionary kata dengan dua operasi. addWord w menyimpan kata w. search p memberi tahu apakah ada kata yang tersimpan dan cocok dengan pola p: panjangnya sama, dan di setiap posisi, pola berisi huruf yang sama atau titik ., yang mewakili satu huruf apa pun.
Operasi i adalah ops[i] pada kata atau pola words[i]. Jalankan operasi tersebut secara berurutan pada dictionary kosong dan kembalikan satu string untuk setiap operasi: "null" untuk addWord, "true" atau "false" untuk search.
Fungsi
- opsstring-array
- operasi-operasi tersebut, sesuai urutan pelaksanaannya
- wordsstring-array
- kata yang akan ditambahkan atau pola yang akan dicari, satu per operasi
- Mengembalikanstring-array
- satu jawaban per operasi, sebagai teks
Batasan
1 ≤ ops.length ≤ 2500words.length == ops.length- Setiap
ops[i]adalahaddWordatausearch. 1 ≤ words[i].length ≤ 20- Sebuah kata yang akan ditambahkan hanya berisi huruf kecil bahasa Inggris.
- Sebuah pola pencarian berisi huruf kecil bahasa Inggris dan paling banyak 3 titik.
Contoh
- Input
- ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
- Output
- ["null", "null", "true", "false", "false", "true"]
- Penjelasan
r.secocok dengan kedua kata: titik menggantikan huruf o padarosedan huruf i padarise. Titik tidak pernah mewakili huruf yang hilang, jadirosdanrose.tidak cocok...s.cocok karena kedua kata memiliki huruf s pada posisi ketiga.
- Input
- ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
- Output
- ["false", "null", "true", "true", "false"]
- Penjelasan
- dictionary dimulai dalam keadaan kosong, jadi
...tidak menemukan apa pun. Setelahskyditambahkan,...dans.ysama-sama cocok dengannya, sedangkanskterlalu pendek.
- Input
- ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
- Output
- ["null", "null", "true", "false", "true"]
- Penjelasan
- Titik pertama pada
ma..obisa berupa p darimapleatau n darimango;mapleberakhir dengan e, tetapimangococok. Tidak ada kata yang berakhir dengan y, jadim...ytidak cocok, danm.p.ecocok denganmaple.
Pertanyaan lanjutan
Bagaimana kamu akan memperluas search jika sebuah pola juga dapat memuat *, yang mewakili rangkaian huruf apa pun, termasuk rangkaian kosong?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Tanpa titik, hash set dari kata-kata yang tersimpan akan menjawab setiap pencarian dengan satu pencarian. Titik mengubah hal itu:
c.tbisa berupacat,cot, ataucut. Struktur apa yang memungkinkan kamu menelusuri kata satu huruf demi satu huruf dan melihat setiap huruf yang bisa muncul berikutnya?Simpan kata-kata dalam trie, dengan penanda pada setiap node tempat kata tersimpan berakhir. Huruf dalam pola mengikuti satu tautan child. Titik dapat mewakili huruf apa pun, jadi kamu harus mencoba setiap child dari node saat ini, lalu kembali saat suatu cabang menemui jalan buntu.
Tulis fungsi rekursif
match(node, i). Di akhir pola, jawab dengan flag akhir milik node. Jika menemukan huruf, ikuti child tersebut, atau gagal jika child tidak ada. Jika menemukan titik, kembalikan true segera setelahmatch(child, i+1)berhasil untuk salah satu child, dan kembalikan false jika tidak ada yang berhasil.
Solusi
Titik berarti pencarian tidak dapat menentukan kata yang dicari: ma..o mewakili 676 kemungkinan kata, dan hanya kata yang tersimpan yang penting. Dalam trie, kata-kata yang memiliki awalan sama berbagi satu jalur. Sebuah huruf dalam pola mengikuti satu tautan, titik menjelajah hanya anak-anak yang ada, dan pencarian mendalam kembali dari cabang yang buntu.
Bandingkan pola dengan setiap kata yang tersimpan
Intuisi
Simpan kata-kata yang ditambahkan dalam sebuah list, lalu uji setiap kata dengan pola: panjangnya sama, dan di setiap posisi terdapat titik atau huruf yang sama. Itulah definisi kecocokan. Periksa pola terhadap setiap kata yang tersimpan agar jawabannya benar.
Setiap pencarian memeriksa seluruh list, dengan biaya O(n·L) untuk n kata yang masing-masing panjangnya hingga L huruf, bahkan untuk pola tanpa titik. 1,250 penambahan diikuti 1,250 pencarian menguji 1,250 × 1,250 = 1,562,500 kata.
Algoritma
- Simpan kata yang ditambahkan dalam sebuah list. Untuk
addWord w, tambahkanwdan catat"null". - Untuk
search p, bandingkanpdengan setiap kata yang panjangnya sama, posisi demi posisi, dengan membiarkan titik menerima huruf apa pun. - Catat
"true"saat pertama kali cocok, atau"false"jika tidak ada yang cocok.
def matches(pattern, word):
# Same length, and every position holds a dot or the same letter.
if len(pattern) != len(word):
return False
for p, w in zip(pattern, word):
if p != "." and p != w:
return False
return True
def wordDictionaryOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "addWord":
stored.append(word)
result.append("null")
else:
found = any(matches(word, s) for s in stored)
result.append("true" if found else "false")
return resultTrie dengan pencarian mendalam pada titik
Intuisi
Masukkan kata-kata ke dalam trie: rose dan rise berbagi node r, lalu bercabang menjadi o dan i. Penanda akhir menunjukkan setiap node tempat sebuah kata tersimpan berakhir. Pola huruf adalah satu jalur menyusuri trie. Titik dapat mewakili huruf apa pun, jadi pada titik, coba setiap child yang ada dan kembalikan true begitu salah satunya menghasilkan kecocokan.
Untuk ma..o, node untuk ma memiliki child p dan n. Melalui p, titik kedua mencapai l, yang tidak memiliki child o, jadi pencarian mundur dan mencoba n: g, lalu o, yang mengakhiri mango.
Kecocokan harus menghabiskan seluruh pola pada node yang ditandai, sehingga panjangnya teratasi: ros berhenti pada node yang tidak ditandai, dan rose. kehabisan tautan. Sebuah titik membuka paling banyak 26 cabang, jadi d titik mengunjungi paling banyak 26^d · L node, dan pola tanpa titik membutuhkan biaya O(L).
Algoritma
- Setiap node memiliki tautan anak dan penanda akhir, yang awalnya tidak aktif.
- Untuk
addWord w: telusuriwdari root, buat node yang belum ada, lalu aktifkan penanda akhir di tempat penelusuran berhenti. match(node, i): jikaisama dengan panjang pola, kembalikan penanda akhir node.- Jika
p[i]adalah huruf, kembalikan false jika anaknya tidak ada, jika tidak, kembalikanmatch(child, i+1). Jika berupa titik, kembalikan true jikamatch(child, i+1)berhasil untuk salah satu anak yang ada, jika tidak, kembalikan false. - Catat
match(root, 0)untuk setiap pencarian,"null"untuk setiap penambahan.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def add_word(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 search(self, pattern):
return self._match(self.root, pattern, 0)
def _match(self, node, pattern, i):
# Can the path below node spell pattern[i:] and end on a stored word?
if i == len(pattern):
return node.is_end
ch = pattern[i]
if ch == ".":
# A dot stands for any letter: try each child until one works.
for child in node.children.values():
if self._match(child, pattern, i + 1):
return True
return False
child = node.children.get(ch)
return child is not None and self._match(child, pattern, i + 1)
def wordDictionaryOps(ops, words):
dictionary = WordDictionary()
result = []
for op, word in zip(ops, words):
if op == "addWord":
dictionary.add_word(word)
result.append("null")
else:
result.append("true" if dictionary.search(word) else "false")
return result
Jebakan dan kasus tepi
- Membiarkan anak pertama menentukan hasil titik. Dalam
ma..o, cabang p gagal dan cabang n berhasil, jadi kode yang mengembalikan hasil anak pertama akan menjawab false saat mencoba p lebih dulu. Jawab false hanya setelah semua anak gagal. - Menjawab true saat pola habis di simpul mana pun. Setelah menambahkan
rose,rosmencapai sebuah simpul, tetapi tidak ada kata yang berakhir di sana. Periksa flag akhir. - Membiarkan titik cocok dengan huruf yang tidak ada.
card.cocok dengancards, tetapi tidak dengancard. - Menganggap titik sebagai huruf. Mengindeks array 26 slot dengan
'.' - 'a'akan membaca di luar array, jadi periksa titik terlebih dahulu.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu Add dan Search Words?
Menambahkan kata dengan panjang L membutuhkan O(L), begitu juga pencarian tanpa titik, berapa pun jumlah kata yang tersimpan. Pencarian dengan d titik membutuhkan O(26^d · L) dalam kasus terburuk. Memori yang dibutuhkan adalah O(T) node untuk T huruf yang ditambahkan.
Bisakah kamu menyelesaikannya dengan hash set, bukan trie?
Ya, dengan kompromi. Sebuah set mencocokkan pola tanpa titik dalam satu pencarian. Untuk pola dengan titik, kamu bisa memindai setiap kata tersimpan dengan panjang tersebut, O(n·L), atau mengganti setiap titik dengan semua 26 huruf lalu mencari setiap hasilnya, sebanyak 17.576 pencarian untuk tiga titik.
Apakah pencarian trie sebaiknya rekursif atau iteratif?
Keduanya bisa digunakan. Rekursi berjalan satu tingkat untuk setiap huruf pola, paling banyak 20 di sini, sehingga tumpukan pemanggilan tetap kecil. Versi iteratif menyimpan tumpukan pasangan (node, position) dan menambahkan setiap anak saat menemukan titik.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def wordDictionaryOps(ops, words):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Output yang diharapkan
["null", "null", "true", "false", "false", "true"]