題目

方法

• 對于每一個節點，初始化一個長度為26的數組，用來存儲對應字母子節點的地址
• 對于每一個節點，初始化一個 $bool$ 變量用來表示是否為葉子節點

代碼

class Trie {
private:vector<Trie*> children = vector<Trie*>(26);bool is_end = false;
public:Trie() {}void insert(string word) {int n = word.size();Trie* node = this;for(int i = 0; i < n; i++){if(node->children[int(word[i]-'a')] == nullptr){node->children[int(word[i]-'a')] = new Trie();}node = node->children[int(word[i]-'a')];}node->is_end = true;}bool search(string word) {int n = word.size();Trie* node = this;for(int i = 0; i < n; i++){if(node->children[int(word[i]-'a')] == nullptr){return false;}node = node->children[int(word[i]-'a')];}return node->is_end;}bool startsWith(string prefix) {int n = prefix.size();Trie* node = this;for(int i = 0; i < n; i++){if(node->children[int(prefix[i]-'a')] == nullptr){return false;}node = node->children[int(prefix[i]-'a')];}return true;}
};/*** 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);*/