今天在練習leetcode時，
看到這樣一個題目: LeetCode- 208. Implement Trie (Prefix Tree)
是一個沒看過的資料結構，查了很多資料之後，
終於大概知道這個資料結構- trie是做什麼用的
trie是一種樹的結構，
用來儲存很多個字串，
優點是它可以快速判斷一個字串是否在trie裡面(可以比BST還快)，
但缺點是trie使用的空間消耗極大，
一個「以空間換取時間」的概念，
我的程式碼如下:
心原一馬
class Trie {
class TrieNode {
public:
vector<TrieNode *> child; //子節點有a~z共26種可能，初始設為null
bool isWord; //記錄某點是否為單字的結尾
TrieNode(): isWord(false), child(vector<TrieNode *>(26, NULL)) {};
};
TrieNode* root; //root為一個空的節點
public:
/** Initialize your data structure here. */
Trie(): root(new TrieNode()) {};
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *p = root;
for (char c : word) {
int i = c - 'a';
if (!p->child[i]){
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 (char c : word) {
int i = c - 'a';
if (!p->child[i]){
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 (char c : prefix) {
int i = c - 'a';
if (!p->child[i]){
return false;
}
p = p->child[i];
}
return true;
}
};
iT 邦幫忙鐵人賽