题目:
Implement a trie with insert, search, and startsWith methods.
思路:
笨办法,容器使用的unordered_set,搜索时逐元素搜索,效率相当相当低,
Runtime: 1080 ms
,不忍直视。
后来我发现,这是一个很重要的数据结构-字典树(如下图)。
我直接学习的https://www.cnblogs.com/grandyang/p/4491665.html,自己是真想不出来。思路就是设计一个多叉树,每个节点保存一个字符。关键是树的节点结构,明白它就全明白了,如下:
class TrieNode{
public:
TrieNode *child[26];
TrieNode():isWord(false){
for (auto &a : child){
a = nullptr;
}
}
bool isWord; // 如果此字符是单词的最后一个字符,则说明到此为止是一个完整的单词。
};
Runtime: 100 ms,运行时间降低了一个量级。
代码实现:
蜗牛代码:
class Trie {
public:
/** Initialize your data structure here. */
unordered_set<string> my_set;
Trie() {
}
/** Inserts a word into the trie. */
void insert(string word) {
my_set.insert(word);
}
/** Returns if the word is in the trie. */
bool search(string word) {
for (auto iter = my_set.begin(); iter != my_set.end(); ++iter){
if (*iter == word){
return true;
}
}
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
for (auto iter = my_set.begin(); iter != my_set.end(); ++iter){
if (iter->find(prefix) == 0){
return true;
}
}
return false;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
更高效的代码:
class TrieNode{
public:
TrieNode *child[26];
TrieNode():isWord(false){
for (auto &a : child){
a = nullptr;
}
}
bool isWord;
};
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *p = root;
for (auto &c : word){
int i = c - 'a';
if (p->child[i] == nullptr){
p->child[i] = new TrieNode();
}
p = p->child[i];
}
p->isWord = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode *p = root;
for(auto &c : word){
int i = c - 'a';
if (p->child[i] == nullptr){
return false;
}
p = p->child[i];
}
return p->isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode *p = root;
for(auto &c : prefix){
int i = c - 'a';
if (p->child[i] == nullptr){
return false;
}
p = p->child[i];
}
return true;
}
private:
TrieNode* root;
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
参考:
https://www.cnblogs.com/grandyang/p/4491665.html
http://dongxicheng.org/structure/trietree/的图