解題思路：

對每一個節(jié)點開一個數(shù)組，數(shù)組大小為26（26個字母），數(shù)組對應的下表就對應兒子節(jié)點的分母。

在插入一個字符串的函數(shù)insert中，程序的邏輯就是：遍歷一次word中的每個字符，如果當前節(jié)點的next數(shù)組中，相應字符的子節(jié)點為null，那就在該數(shù)組位置上創(chuàng)建一個新的Trie對象。遍歷完一個word之后，在最后的字符節(jié)點上，需要將其is_str置為true。

?

class Trie { public:bool is_str; //用于標記該節(jié)點是否是單詞末尾Trie *next[26];/** Initialize your data structure here. */Trie() {is_str = false;memset(next, 0, sizeof(next)); //每次新建一個Trie對象，都需要將其next數(shù)組清0}/** Inserts a word into the trie. */void insert(string word) {Trie *cur = this;for(auto w: word){if(cur->next[w - 'a'] == NULL){ //下一個節(jié)點不存在，就生成下一個Trie節(jié)點Trie* newnode = new Trie();cur->next[w - 'a'] = newnode;}cur = cur->next[w - 'a'];}cur->is_str = true; //遍歷完一個字符串之后，就將最后一個字符的is_str設為true，表明到達一個單詞的最后一個字符}/** Returns if the word is in the trie. */bool search(string word) {Trie* cur = this;for(auto w: word){if(cur != NULL) cur = cur->next[w - 'a'];}return (cur != NULL && cur->is_str); //判斷是否是一個詞，需要滿足兩個條件，非null和is_str為true}/** Returns if there is any word in the trie that starts with the given prefix. */bool startsWith(string prefix) {Trie* cur = this;for(auto w: prefix){if(cur != NULL) cur = cur->next[w - 'a'];}return (cur != NULL); //只需判斷是否為null} };/*** 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);*/

?

?

?

總結

以上是生活随笔為你收集整理的Leetcode 208. 实现 Trie (前缀树) 解题思路及C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。