代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.void insert(String word) Inserts the string word into the trie.int countWordsEqualTo(String word) Returns the number of instances of the string word in the trie.int countWordsStartingWith(String prefix) Returns the number of strings in the trie that have the string prefix as a prefix.void erase(String word) Erases the string word from the trie.
Example 1:
Input
["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"]
[[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]]
Output
[null, null, null, 2, 2, null, 1, 1, null, 0]
Explanation
Trie trie = new Trie();
trie.insert("apple"); // Inserts "apple".
trie.insert("apple"); // Inserts another "apple".
trie.countWordsEqualTo("apple"); // There are two instances of "apple" so return 2.
trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2.
trie.erase("apple"); // Erases one "apple".
trie.countWordsEqualTo("apple"); // Now there is only one instance of "apple" so return 1.
trie.countWordsStartingWith("app"); // return 1
trie.erase("apple"); // Erases "apple". Now the trie is empty.
trie.countWordsStartingWith("app"); // return 0
Constraints:
1 <= word.length, prefix.length <= 2000word and prefix consist only of lowercase English letters.3 * 104 calls in total will be made to insert, countWordsEqualTo, countWordsStartingWith, and erase.erase, the string word will exist in the trie.class Trie:
def __init__(self):
self.children = [None] * 26
self.count = 0
self.pre_count = 0
def insert(self, word: str) -> None:
node = self
for c in word:
index = ord(c) - ord('a')
if node.children[index] is None:
node.children[index] = Trie()
node = node.children[index]
node.pre_count += 1
node.count += 1
def countWordsEqualTo(self, word: str) -> int:
node = self._search_prefix(word)
return 0 if node is None else node.count
def countWordsStartingWith(self, prefix: str) -> int:
node = self._search_prefix(prefix)
return 0 if node is None else node.pre_count
def erase(self, word: str) -> None:
node = self
for c in word:
index = ord(c) - ord('a')
node = node.children[index]
node.pre_count -= 1
node.count -= 1
def _search_prefix(self, prefix: str):
node = self
for c in prefix:
index = ord(c) - ord('a')
if node.children[index] is None:
return None
node = node.children[index]
return node
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.countWordsEqualTo(word)
# param_3 = obj.countWordsStartingWith(prefix)
# obj.erase(word)
class Trie {
private Trie[] children;
private int count;
private int preCount;
public Trie() {
children = new Trie[26];
count = 0;
preCount = 0;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); ++i) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
node.preCount += 1;
}
node.count += 1;
}
public int countWordsEqualTo(String word) {
Trie node = searchPrefix(word);
return node == null ? 0 : node.count;
}
public int countWordsStartingWith(String prefix) {
Trie node = searchPrefix(prefix);
return node == null ? 0 : node.preCount;
}
public void erase(String word) {
Trie node = this;
for (int i = 0; i < word.length(); ++i) {
int index = word.charAt(i) - 'a';
node = node.children[index];
node.preCount -= 1;
}
node.count -= 1;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); ++i) {
int index = prefix.charAt(i) - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* int param_2 = obj.countWordsEqualTo(word);
* int param_3 = obj.countWordsStartingWith(prefix);
* obj.erase(word);
*/
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
