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

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

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

[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

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++實現(xiàn)LeetCode(208.實現(xiàn)字典樹(前綴樹))的文章就介紹到這了,更多相關(guān)C++實現(xiàn)實現(xiàn)字典樹(前綴樹)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言實現(xiàn)獲取內(nèi)存信息并輸出的實例

    C語言實現(xiàn)獲取內(nèi)存信息并輸出的實例

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

    CreateThread()與beginthread()的區(qū)別詳細解析

    很多開發(fā)者不清楚這兩者之間的關(guān)系,他們隨意選一個函數(shù)來用,發(fā)現(xiàn)也沒有什么大問題,于是就忙于解決更為緊迫的任務(wù)去了。等到有一天忽然發(fā)現(xiàn)一個程序運行時間很長的時候會有細微的內(nèi)存泄露,開發(fā)者絕對不會想到是因為這兩套函數(shù)用混的結(jié)果
    2013-09-09
  • C語言實現(xiàn)宿舍管理系統(tǒng)設(shè)計

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

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

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

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

    深入解析C++編程中的運算符重載

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

    淺析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用

    下面小編就為大家?guī)硪黄獪\析C/C++中動態(tài)鏈接庫的創(chuàng)建和調(diào)用。小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考,一起跟隨小編過來看看吧
    2016-05-05
  • C++中jsoncpp庫和nlohmann-json庫實現(xiàn)JSON與字符串類型轉(zhuǎn)換

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

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

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

    C++深入講解對象的銷毀之析構(gòu)函數(shù)

    構(gòu)造函數(shù)在創(chuàng)建對象時被系統(tǒng)自動調(diào)用,而析構(gòu)函數(shù)(Destructor)在對象被撤銷時被自動調(diào)用,相比構(gòu)造函數(shù),析構(gòu)函數(shù)要簡單的多
    2022-04-04
  • 基于C語言實現(xiàn)簡單的12306火車售票系統(tǒng)

    基于C語言實現(xiàn)簡單的12306火車售票系統(tǒng)

    火車售票系統(tǒng)給我們的出行帶來了極大的方面,那么他基于編程是如何實現(xiàn)的呢?今天小編抽時間給大家分享一個使用C語言寫的一個簡單的火車票系統(tǒng),感興趣的朋友參考下
    2016-09-09

最新評論