C++實現(xiàn)LeetCode(208.實現(xiàn)字典樹(前綴樹))
[LeetCode] 208. Implement Trie (Prefix Tree) 實現(xiàn)字典樹(前綴樹)
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
- You may assume that all inputs are consist of lowercase letters a-z.
- All inputs are guaranteed to be non-empty strings.
這道題讓我們實現(xiàn)一個重要但又有些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)-字典樹, 又稱前綴樹或單詞查找樹,例如,一個保存了8個鍵的trie結(jié)構(gòu),"A", "to", "tea", "ted", "ten", "i", "in", and "inn"。
字典樹主要有如下三點性質(zhì):
1. 根節(jié)點不包含字符,除根節(jié)點意外每個節(jié)點只包含一個字符。
2. 從根節(jié)點到某一個節(jié)點,路徑上經(jīng)過的字符連接起來,為該節(jié)點對應(yīng)的字符串。
3. 每個節(jié)點的所有子節(jié)點包含的字符串不相同。
字母樹的插入(Insert)、刪除( Delete)和查找(Find)都非常簡單,用一個一重循環(huán)即可,即第i 次循環(huán)找到前i 個字母所對應(yīng)的子樹,然后進行相應(yīng)的操作。實現(xiàn)這棵字母樹,我們用最常見的數(shù)組保存(靜態(tài)開辟內(nèi)存)即可,當然也可以開動態(tài)的指針類型(動態(tài)開辟內(nèi)存)。至于結(jié)點對兒子的指向,一般有三種方法:
1、對每個結(jié)點開一個字母集大小的數(shù)組,對應(yīng)的下標是兒子所表示的字母,內(nèi)容則是這個兒子對應(yīng)在大數(shù)組上的位置,即標號;
2、對每個結(jié)點掛一個鏈表,按一定順序記錄每個兒子是誰;
3、使用左兒子右兄弟表示法記錄這棵樹。
三種方法,各有特點。第一種易實現(xiàn),但實際的空間要求較大;第二種,較易實現(xiàn),空間要求相對較小,但比較費時;第三種,空間要求最小,但相對費時且不易寫。
我們這里只來實現(xiàn)第一種方法,這種方法實現(xiàn)起來簡單直觀,字母的字典樹每個節(jié)點要定義一個大小為 26 的子節(jié)點指針數(shù)組,然后用一個標志符用來記錄到當前位置為止是否為一個詞,初始化的時候講 26 個子節(jié)點都賦為空。那么 insert 操作只需要對于要插入的字符串的每一個字符算出其的位置,然后找是否存在這個子節(jié)點,若不存在則新建一個,然后再查找下一個。查找詞和找前綴操作跟 insert 操作都很類似,不同點在于若不存在子節(jié)點,則返回 false。查找次最后還要看標識位,而找前綴直接返回 true 即可。代碼如下:
class TrieNode { public: TrieNode *child[26]; bool isWord; TrieNode(): isWord(false) { for (auto &a : child) a = nullptr; } }; class Trie { public: Trie() { root = new TrieNode(); } void insert(string s) { TrieNode *p = root; for (auto &a : s) { int i = a - 'a'; if (!p->child[i]) p->child[i] = new TrieNode(); p = p->child[i]; } p->isWord = true; } bool search(string key) { TrieNode *p = root; for (auto &a : key) { int i = a - 'a'; if (!p->child[i]) return false; p = p->child[i]; } return p->isWord; } bool startsWith(string prefix) { TrieNode *p = root; for (auto &a : prefix) { int i = a - 'a'; if (!p->child[i]) return false; p = p->child[i]; } return true; } private: TrieNode* root; };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/208
類似題目:
Add and Search Word - Data structure design
Design Search Autocomplete System
參考資料:
https://leetcode.com/problems/implement-trie-prefix-tree/
到此這篇關(guān)于C++實現(xiàn)LeetCode(208.實現(xiàn)字典樹(前綴樹))的文章就介紹到這了,更多相關(guān)C++實現(xiàn)實現(xiàn)字典樹(前綴樹)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
CreateThread()與beginthread()的區(qū)別詳細解析
很多開發(fā)者不清楚這兩者之間的關(guān)系,他們隨意選一個函數(shù)來用,發(fā)現(xiàn)也沒有什么大問題,于是就忙于解決更為緊迫的任務(wù)去了。等到有一天忽然發(fā)現(xiàn)一個程序運行時間很長的時候會有細微的內(nèi)存泄露,開發(fā)者絕對不會想到是因為這兩套函數(shù)用混的結(jié)果2013-09-09C語言實現(xiàn)宿舍管理系統(tǒng)設(shè)計
這篇文章主要為大家詳細介紹了C語言實現(xiàn)宿舍管理系統(tǒng)設(shè)計,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-03-03vs2019配置Qt5開發(fā)環(huán)境(圖文教程)
本文主要介紹了如何使用visual studi2019配置qt5開發(fā)環(huán)境,以及創(chuàng)建qt項目,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-12-12淺析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用
下面小編就為大家?guī)硪黄獪\析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用。小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考,一起跟隨小編過來看看吧2016-05-05C++中jsoncpp庫和nlohmann-json庫實現(xiàn)JSON與字符串類型轉(zhuǎn)換
jsoncpp是ROS自帶的一個JSON庫,它提供了一些函數(shù)來解析和生成JSON數(shù)據(jù),在ROS中,可以使用jsoncpp庫來實現(xiàn)JSON與字符串類型之間的轉(zhuǎn)換,這篇文章主要介紹了jsoncpp庫和nlohmann-json庫實現(xiàn)JSON與字符串類型轉(zhuǎn)換,需要的朋友可以參考下2023-08-08C++ vector容器 find erase的使用操作:查找并刪除指定元素
這篇文章主要介紹了C++ vector容器 find erase的使用操作:查找并刪除指定元素,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-05-05基于C語言實現(xiàn)簡單的12306火車售票系統(tǒng)
火車售票系統(tǒng)給我們的出行帶來了極大的方面,那么他基于編程是如何實現(xiàn)的呢?今天小編抽時間給大家分享一個使用C語言寫的一個簡單的火車票系統(tǒng),感興趣的朋友參考下2016-09-09