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

C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計)

 更新時間:2021年08月09日 14:25:32   作者:Grandyang  
這篇文章主要介紹了C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 211.Add and Search Word - Data structure design 添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

LeetCode出新題的速度越來越快了,有點跟不上節(jié)奏的感覺了。這道題如果做過之前的那道 Implement Trie (Prefix Tree) 實現(xiàn)字典樹(前綴樹)的話就沒有太大的難度了,還是要用到字典樹的結(jié)構(gòu),唯一不同的地方就是search的函數(shù)需要重新寫一下,因為這道題里面'.'可以代替任意字符,所以一旦有了'.',就需要查找所有的子樹,只要有一個返回true,整個search函數(shù)就返回true,典型的DFS的問題,其他部分跟上一道實現(xiàn)字典樹沒有太大區(qū)別,代碼如下:

class WordDictionary {
public:
    struct TrieNode {
    public:
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) {
            for (auto &a : child) a = NULL;
        }
    };
    
    WordDictionary() {
        root = new TrieNode();
    }
    
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode *p = root;
        for (auto &a : word) {
            int i = a - 'a';
            if (!p->child[i]) p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return searchWord(word, root, 0);
    }
    
    bool searchWord(string &word, TrieNode *p, int i) {
        if (i == word.size()) return p->isWord;
        if (word[i] == '.') {
            for (auto &a : p->child) {
                if (a && searchWord(word, a, i + 1)) return true;
            }
            return false;
        } else {
            return p->child[word[i] - 'a'] && searchWord(word, p->child[word[i] - 'a'], i + 1);
        }
    }
    
private:
    TrieNode *root;
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

討論:這道題有個很好的Follow up,就是當(dāng)搜索的單詞中存在星號怎么搞,星號的定義和Wildcard Matching中一樣,可以代表任意的字符串,包括空字符串,請參見評論區(qū)1樓。

類似題目:

Implement Trie (Prefix Tree)

Wildcard Matching

參考資料:

https://leetcode.com/discuss/36246/my-java-trie-based-solution

到此這篇關(guān)于C++實現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言實現(xiàn)紙牌24點小游戲

    C語言實現(xiàn)紙牌24點小游戲

    這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)紙牌24點小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-10-10
  • VC小技巧匯總之窗口技巧

    VC小技巧匯總之窗口技巧

    這篇文章主要介紹了VC小技巧匯總之窗口技巧,功能非常實用,對于VC開發(fā)有一定借鑒價值,需要的朋友可以參考下
    2014-07-07
  • C++關(guān)于類結(jié)構(gòu)體大小和構(gòu)造順序,析構(gòu)順序的測試詳解

    C++關(guān)于類結(jié)構(gòu)體大小和構(gòu)造順序,析構(gòu)順序的測試詳解

    這篇文章主要介紹了C++類結(jié)構(gòu)體大小和構(gòu)造順序,析構(gòu)順序的測試,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-08-08
  • C++中如何實現(xiàn)回調(diào)的方法示例

    C++中如何實現(xiàn)回調(diào)的方法示例

    這篇文章主要給大家介紹了關(guān)于C++中如何實現(xiàn)回調(diào)的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用c++具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2017-10-10
  • C語言菜鳥基礎(chǔ)教程之判斷

    C語言菜鳥基礎(chǔ)教程之判斷

    C語言判斷結(jié)構(gòu)要求程序員指定一個或多個要評估或測試的條件,以及條件為真時要執(zhí)行的語句(必需的)和條件為假時要執(zhí)行的語句(可選的)
    2017-10-10
  • C 語言中strstr函數(shù)實例詳解

    C 語言中strstr函數(shù)實例詳解

    這篇文章主要介紹了C 語言中strstr函數(shù)實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-07-07
  • C++實現(xiàn)LeetCode(29.兩數(shù)相除)

    C++實現(xiàn)LeetCode(29.兩數(shù)相除)

    這篇文章主要介紹了C++實現(xiàn)LeetCode(29.兩數(shù)相除),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • 詳解C語言中const關(guān)鍵字的用法

    詳解C語言中const關(guān)鍵字的用法

    這篇文章主要對C語言中const關(guān)鍵字的用法進行了詳細(xì)的分析介紹,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2015-08-08
  • C++中typedef 及其與struct的結(jié)合使用

    C++中typedef 及其與struct的結(jié)合使用

    這篇文章主要介紹了C++中typedef 及其與struct的結(jié)合使用,需要的朋友可以參考下
    2014-02-02
  • C++ SOCKET多線程實現(xiàn)聊天小程序

    C++ SOCKET多線程實現(xiàn)聊天小程序

    這篇文章主要為大家詳細(xì)介紹了C++ SOCKET多線程實現(xiàn)聊天小程序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-06-06

最新評論