題目:
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/的圖