Implement Trie (Prefix Tree)
Hãy xây dựng một trie (cây tiền tố) cho các từ viết thường với ba thao tác: insert w thêm từ w, search w cho biết liệu chính từ w đã được thêm vào hay chưa, và startsWith p cho biết liệu có từ nào đã được thêm vào bắt đầu bằng p hay không. Một từ cũng được tính là tiền tố của chính nó.
Thao tác i là ops[i] trên words[i]. Hãy thực hiện lần lượt các thao tác trên một trie rỗng và trả về một chuỗi cho mỗi thao tác: "null" đối với thao tác thêm, "true" hoặc "false" đối với thao tác tìm kiếm hoặc startsWith.
Hàm
- opsstring-array
- các thao tác, theo thứ tự chúng chạy
- wordsstring-array
- từ hoặc tiền tố cho mỗi phép toán
- Trả vềstring-array
- một câu trả lời cho mỗi phép toán, dưới dạng văn bản
Ràng buộc
1 ≤ ops.length ≤ 2000words.length == ops.length- Mỗi
ops[i]làinsert,searchhoặcstartsWith. 1 ≤ words[i].length ≤ 20words[i]chỉ chứa các chữ cái tiếng Anh viết thường.
Ví dụ
- Đầu vào
- ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
- Đầu ra
- ["null", "false", "true", "null", "true"]
- Giải thích
carlà phần đầu củacard, nênstartsWith carlà"true", nhưngcarchưa bao giờ được thêm vào, nên lần tìm kiếm đầu tiên trả về"false". Sau khiinsert car, lần tìm kiếm sẽ tìm thấy nó.
- Đầu vào
- ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
- Đầu ra
- ["null", "null", "true", "false", "false", "true", "true"]
- Giải thích
- Cả hai từ đều bắt đầu bằng
tenhưng không từ nào chính xác làte, vì vậy startsWith là"true"còn search là"false". Không có từ nào bắt đầu bằngtex, vàtealà tiền tố của chính nó.
- Đầu vào
- ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
- Đầu ra
- ["false", "false", "null", "true", "false", "true"]
- Giải thích
- Trong trie rỗng, cả hai truy vấn đều trả về
"false". Sau khiinsert dog, thao tác tìm kiếm tìm thấy từ này, không có từ nào bắt đầu bằngdogs, vàdolà tiền tố củadog.
Câu hỏi mở rộng
Làm thế nào để thêm thao tác countPrefix p trả về số từ riêng biệt đã lưu bắt đầu bằng p, vẫn trong thời gian O(L)?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Một tập hợp các từ hoàn chỉnh có thể trả lời
searchchỉ với một lần tra cứu, nhưng không thể cho bạn biết có từ nào bắt đầu bằngtehay không nếu không kiểm tra từng từ. Sẽ thế nào nếu các từ có cùng phần đầu dùng chung nơi lưu trữ phần đầu đó?Xây dựng một cây trong đó mỗi nút đại diện cho một tiền tố và có một liên kết đến nút con cho mỗi chữ cái có thể xuất hiện tiếp theo. Khi đó, một từ là một đường đi bắt đầu từ nút gốc. Thêm vào mỗi nút một cờ cho biết có từ nào được lưu kết thúc chính xác tại đó hay không.
Mỗi thao tác duyệt các chữ cái từ nút gốc.
inserttạo các nút còn thiếu và bật cờ ở nút cuối cùng.startsWiththành công khi quá trình duyệt đến cuối;searchcũng cần cờ được bật tại nút mà nó dừng lại.
Lời giải
Tập hợp băm xử lý truy vấn search, nhưng nó không có khái niệm về phần đầu, nên startsWith sẽ phải quét mọi từ. Trie lưu mỗi từ thành một đường đi gồm các chữ cái bắt đầu từ nút gốc: những từ có cùng phần đầu sẽ dùng chung một đường đi, còn một cờ đánh dấu vị trí kết thúc của từ đã lưu. Cả hai truy vấn đều trở thành một lần duyệt với nhiều nhất L liên kết.
Giữ một danh sách từ và quét danh sách đó
Ý tưởng
Giữ mọi từ đã thêm trong một danh sách. search w so sánh w với từng từ đã lưu, còn startsWith p kiểm tra xem có từ nào đã lưu bắt đầu bằng p hay không. Cách này đúng vì kiểm tra trực tiếp định nghĩa. Với n từ đã lưu, mỗi truy vấn cần tối đa n lần so sánh, mỗi lần so sánh tối đa L ký tự: 1,000 từ và 1,000 truy vấn tạo ra một triệu lần so sánh chuỗi.
Thuật toán
- Bắt đầu với một danh sách rỗng.
insert w: thêmwvào cuối danh sách.search w: trả về liệu có từ nào đã lưu bằngwhay không.startsWith p: trả về liệu có từ nào đã lưu bắt đầu bằngphay không.
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 resultMột trie: các liên kết đến nút con và cờ đánh dấu kết thúc
Ý tưởng
Mỗi nút đại diện cho một tiền tố, gồm các chữ cái trên đường đi từ nút gốc đến nút đó. Nút giữ một liên kết đến nút con cho mỗi chữ cái có thể xuất hiện tiếp theo (26 vị trí hoặc một bản đồ) và một cờ isEnd cho biết một từ đã lưu có kết thúc chính xác tại đó hay không. Chèn tea sẽ tạo các nút cho t, te và tea; sau đó chèn ten chỉ thêm ten, vì hai từ có chung đường đi cho te.
Đường đi gặp một liên kết bị thiếu chứng tỏ không có từ đã lưu nào bắt đầu bằng những chữ cái đó: tex dừng ở te, vì nút này không có liên kết x. Đường đi đến cuối sẽ dừng tại nút ứng với truy vấn, vì vậy startsWith là true và search trả lời dựa trên cờ. Nút te tồn tại nhưng cờ của nó tắt, nên search te là false. Mỗi thao tác đi theo nhiều nhất L liên kết, bất kể có bao nhiêu từ được lưu, và trie chứa một nút cho mỗi tiền tố riêng biệt.
Thuật toán
- Tạo nút gốc không có liên kết đến nút con và tắt
isEnd. insert w: từ nút gốc, đi theo liên kết ứng với từng chữ cái, tạo nút nếu chưa có. BậtisEndở nút cuối.find(p): từ nút gốc, đi theo liên kết ứng với từng chữ cái; trả về không có gì ngay khi thiếu một liên kết, nếu không thì trả về nút đã đến.search w: trả về true khifind(w)trả về một nút cóisEndđược bật.startsWith p: trả về true khifind(p)trả về một nút.
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
Lỗi thường gặp và trường hợp biên
- Để
searchtrả về true bất cứ khi nào đường dẫn tồn tại. Sauinsert card, đường dẫn đếncartồn tại, nhưngsearch carphải trả về false. - Chỉ đặt
isEndtrên các nút mới được tạo. Chèncardsaucardskhông tạo ra nút nào, nhưng nút cuối cùng cần có cờ này. - Tạo nút con mới khi liên kết đã tồn tại. Chèn
tenbằng một núttmới sẽ làm mấttea. - Đọc quá cuối đường dẫn.
startsWith sunnykhi chỉ lưusunphải dừng ở liên kết đầu tiên bị thiếu và trả về false.
Câu hỏi thường gặp3
Độ phức tạp thời gian của trie là gì?
Insert, search và startsWith đều đi theo một liên kết cho mỗi chữ cái, nên mỗi thao tác mất O(L) với một từ dài L, bất kể có bao nhiêu từ được lưu trữ. Cấu trúc này cần O(T) nút cho tổng cộng T chữ cái đã chèn, mỗi nút chứa tối đa 26 liên kết đến nút con.
Tại sao dùng trie thay vì tập hợp băm?
Tập hợp băm tìm từ đầy đủ trong O(L) nhưng không thể trả lời câu hỏi về tiền tố nếu không quét mọi từ. Lưu mọi tiền tố trong một tập hợp thứ hai tốn 210 ký tự cho một từ dài 20 ký tự. Trie lưu mỗi tiền tố chung một lần và trả lời cả hai câu hỏi chỉ bằng một lượt duyệt.
Nút trong trie nên dùng mảng gồm 26 liên kết hay bảng băm?
Mảng tìm nút con bằng một chỉ số nhưng tốn 26 ô cho mỗi nút, ngay cả khi nút chỉ có một nút con. Bản đồ chỉ lưu những nút con hiện có và hoạt động với mọi bảng chữ cái, đổi lại phải tính mã băm cho mỗi chữ cái. Với chữ cái tiếng Anh viết thường, cách nào cũng dùng được; với Unicode hoặc trie thưa, bản đồ tiết kiệm bộ nhớ hơn.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def trieOps(ops, words):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
ops = ["insert", "search", "startsWith", "insert", "search"] words = ["card", "car", "car", "car", "car"]
Đầu ra mong đợi
["null", "false", "true", "null", "true"]