欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)LeetCode(208.實(shí)現(xiàn)字典樹(前綴樹))

 更新時(shí)間:2021年08月09日 14:26:31   作者:Grandyang  
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(208.實(shí)現(xiàn)字典樹(前綴樹)),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[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

Replace Words

Implement Magic Dictionary

參考資料:

https://leetcode.com/problems/implement-trie-prefix-tree/

https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58832/AC-JAVA-solution-simple-using-single-array

https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58986/Concise-O(1)-JAVA-solution-based-on-HashMap

https://leetcode.com/problems/implement-trie-prefix-tree/discuss/58842/Maybe-the-code-is-not-too-much-by-using-%22next26%22-C%2B%2B

到此這篇關(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í)例

    這篇文章主要介紹了C語言實(shí)現(xiàn)獲取內(nèi)存信息并輸出的實(shí)例的相關(guān)資料,需要的朋友可以參考下
    2017-03-03
  • CreateThread()與beginthread()的區(qū)別詳細(xì)解析

    CreateThread()與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-09
  • C語言實(shí)現(xiàn)宿舍管理系統(tǒng)設(shè)計(jì)

    C語言實(shí)現(xiàn)宿舍管理系統(tǒng)設(shè)計(jì)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)宿舍管理系統(tǒng)設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • vs2019配置Qt5開發(fā)環(huán)境(圖文教程)

    vs2019配置Qt5開發(fā)環(huán)境(圖文教程)

    本文主要介紹了如何使用visual studi2019配置qt5開發(fā)環(huán)境,以及創(chuàng)建qt項(xiàng)目,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-12-12
  • 深入解析C++編程中的運(yùn)算符重載

    深入解析C++編程中的運(yùn)算符重載

    這篇文章主要介紹了C++編程中的運(yùn)算符重載,運(yùn)算符重載是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2016-04-04
  • 淺析C/C++中動(dòng)態(tài)鏈接庫的創(chuàng)建和調(diào)用

    淺析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-05
  • C++中jsoncpp庫和nlohmann-json庫實(shí)現(xiàn)JSON與字符串類型轉(zhuǎn)換

    C++中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-08
  • C++ vector容器 find erase的使用操作:查找并刪除指定元素

    C++ vector容器 find erase的使用操作:查找并刪除指定元素

    這篇文章主要介紹了C++ vector容器 find erase的使用操作:查找并刪除指定元素,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2021-05-05
  • C++深入講解對(duì)象的銷毀之析構(gòu)函數(shù)

    C++深入講解對(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)

    基于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

最新評(píng)論