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