動機
就是trie
Problem
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 stringword
into the trie.boolean search(String word)
Returnstrue
if the stringword
is in the trie (i.e., was inserted before), andfalse
otherwise.boolean startsWith(String prefix)
Returnstrue
if there is a previously inserted stringword
that has the prefixprefix
, andfalse
otherwise.
Example 1:
Input[Trie, insert, search, search, startsWith, insert, search][[], [apple], [apple], [app], [app], [app], [app]]Output[null, null, true, false, true, null, true]ExplanationTrie trie = new Trie();trie.insert(apple);trie.search(apple); // return Truetrie.search(app); // return Falsetrie.startsWith(app); // return Truetrie.insert(app);trie.search(app); // return True
Constraints:
1 <= word.length, prefix.length <= 2000
word
andprefix
consist only of lowercase English letters.- At most
3 * 104
calls in total will be made toinsert
,search
, andstartsWith
.
Sol
每一個node有[flag :: bool, hash{char -> Node}]
flag是指到此是不是某個單字的終點
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.t = [False, {}]
def insert(self, w: str) -> None:
"""
Inserts a word into the trie.
"""
tmp = self.t
for c in w:
if c not in tmp[1]:
tmp[1][c] = [False, {}]
tmp = tmp[1][c]
tmp[0] = True
def search(self, w: str) -> bool:
"""
Returns if the word is in the trie.
"""
tmp = self.t
for c in w:
if c not in tmp[1]:
return False
tmp = tmp[1][c]
return tmp[0]
def startsWith(self, p: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
tmp = self.t
for c in p:
if c not in tmp[1]:
return False
tmp = tmp[1][c]
return True
另外有C++版
struct Trie {
unordered_map<char, struct Trie*> nextLevel;
bool end;
~Trie() {
for (auto& kv : nextLevel) {
delete kv.second;
}
}
void insert(string s) {
Trie* trie = this;
for (auto& c : s) {
if (trie->nextLevel.find(c) == trie->nextLevel.end()) {
trie->nextLevel[c] = new Trie();
}
trie = trie->nextLevel[c];
}
trie->end = 1;
}
bool search(string s) {
Trie* trie = this;
for (auto& c : s) {
if (trie->nextLevel.find(c) != trie->nextLevel.end()) {
trie = trie->nextLevel[c];
} else {
return 0;
}
}
return trie->end;
}
bool startsWith(string s) {
Trie* trie = this;
for (auto& c : s) {
if (trie->nextLevel.find(c) != trie->nextLevel.end()) {
trie = trie->nextLevel[c];
} else {
return 0;
}
}
return 1;
}
};