亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C++實(shí)現(xiàn)LeetCode(676.實(shí)現(xiàn)神奇字典)

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

[LeetCode] 676.Implement Magic Dictionary 實(shí)現(xiàn)神奇字典

Implement a magic directory with buildDict, and search methods.

For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.

For the method search, you'll be given a word, and judge whether if you modify exactly one character into another character in this word, the modified word is in the dictionary you just built.

Example 1:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False

Note:

  1. You may assume that all the inputs are consist of lowercase letters a-z.
  2. For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
  3. Please remember to RESET your class variables declared in class MagicDictionary, as static/class variables are persisted across multiple test cases. Please see here for more details.

這道題讓我們?cè)O(shè)計(jì)一種神奇字典的數(shù)據(jù)結(jié)構(gòu),里面有一些單詞,實(shí)現(xiàn)的功能是當(dāng)我們搜索一個(gè)單詞,只有存在和這個(gè)單詞只有一個(gè)位置上的字符不相同的才能返回true,否則就返回false,注意完全相同也是返回false,必須要有一個(gè)字符不同。博主首先想到了One Edit Distance那道題,只不過(guò)這道題的兩個(gè)單詞之間長(zhǎng)度必須相等。所以只需檢測(cè)和要搜索單詞長(zhǎng)度一樣的單詞即可,所以我們用的數(shù)據(jù)結(jié)構(gòu)就是根據(jù)單詞的長(zhǎng)度來(lái)分,把長(zhǎng)度相同相同的單詞放到一起,這樣就可以減少搜索量。那么對(duì)于和要搜索單詞進(jìn)行比較的單詞,由于已經(jīng)保證了長(zhǎng)度相等,我們直接進(jìn)行逐個(gè)字符比較即可,用cnt表示不同字符的個(gè)數(shù),初始化為0。如果當(dāng)前遍歷到的字符相等,則continue;如果當(dāng)前遍歷到的字符不相同,并且此時(shí)cnt已經(jīng)為1了,則break,否則cnt就自增1。退出循環(huán)后,我們檢測(cè)是否所有字符都比較完了且cnt為1,是的話則返回true,否則就是跟下一個(gè)詞比較。如果所有詞都比較完了,則返回false,參見(jiàn)代碼如下:

解法一:

class MagicDictionary {
public:
    /** Initialize your data structure here. */
    MagicDictionary() {}
    
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for (string word : dict) {
            m[word.size()].push_back(word);
        }
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        for (string str : m[word.size()]) {
            int cnt = 0, i = 0;
            for (; i < word.size(); ++i) {
                if (word[i] == str[i]) continue;
                if (word[i] != str[i] && cnt == 1) break; 
                ++cnt;
            }
            if (i == word.size() && cnt == 1) return true;
        }
        return false;
    }

private:
    unordered_map<int, vector<string>> m;
};

下面這種解法實(shí)際上是用到了前綴樹(shù)中的search的思路,但是我們又沒(méi)有整個(gè)用到prefix tree,博主感覺(jué)那樣寫(xiě)法略復(fù)雜,其實(shí)我們只需要借鑒一下search方法就行了。我們首先將所有的單詞都放到一個(gè)集合中,然后在search函數(shù)中,我們遍歷要搜索的單詞的每個(gè)字符,然后把每個(gè)字符都用a-z中的字符替換一下,形成一個(gè)新詞,當(dāng)然遇到本身要跳過(guò)。然后在集合中看是否存在,存在的話就返回true。記得換完一圈字符后要換回去,不然就不滿(mǎn)足只改變一個(gè)字符的條件了,參見(jiàn)代碼如下:

解法二:

class MagicDictionary {
public:
    /** Initialize your data structure here. */
    MagicDictionary() {}
    
    /** Build a dictionary through a list of words */
    void buildDict(vector<string> dict) {
        for (string word : dict) s.insert(word);
    }
    
    /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    bool search(string word) {
        for (int i = 0; i < word.size(); ++i) {
            char t = word[i];
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == t) continue;
                word[i] = c;
                if (s.count(word)) return true;
            }
            word[i] = t;
        }
        return false;
    }
    
private:
    unordered_set<string> s;
};

類(lèi)似題目:

Implement Trie (Prefix Tree)

參考資料:

https://discuss.leetcode.com/topic/103004/c-clean-code

https://discuss.leetcode.com/topic/102992/easy-14-lines-java-solution-hashmap

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(676.實(shí)現(xiàn)神奇字典)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)實(shí)現(xiàn)神奇字典內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++一個(gè)函數(shù)如何調(diào)用其他.cpp文件中的函數(shù)

    C++一個(gè)函數(shù)如何調(diào)用其他.cpp文件中的函數(shù)

    這篇文章主要介紹了C++一個(gè)函數(shù)如何調(diào)用其他.cpp文件中的函數(shù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • 淺析C++中結(jié)構(gòu)體的定義、初始化和引用

    淺析C++中結(jié)構(gòu)體的定義、初始化和引用

    以下是對(duì)C++中結(jié)構(gòu)體的定義、初始化和引用進(jìn)行了詳細(xì)的介紹,需要的朋友可以過(guò)來(lái)參考下
    2013-09-09
  • C++常用函數(shù)之XML JSON格式轉(zhuǎn)換問(wèn)題

    C++常用函數(shù)之XML JSON格式轉(zhuǎn)換問(wèn)題

    XML在Json出現(xiàn)前應(yīng)用很廣泛,靈活性好,應(yīng)用語(yǔ)言也沒(méi)有限制,發(fā)展了這么長(zhǎng)時(shí)間后xml標(biāo)準(zhǔn)已經(jīng)很臃腫。這篇文章主要介紹了C++常用函數(shù)之XML JSON格式轉(zhuǎn)換問(wèn)題,需要的朋友可以參考下
    2020-02-02
  • C++11?成員函數(shù)作為回調(diào)函數(shù)的使用方式

    C++11?成員函數(shù)作為回調(diào)函數(shù)的使用方式

    這篇文章主要介紹了C++11?成員函數(shù)作為回調(diào)函數(shù)的使用方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-11-11
  • 詳細(xì)理解函C語(yǔ)言的函數(shù)棧幀

    詳細(xì)理解函C語(yǔ)言的函數(shù)棧幀

    這篇文章主要為大家介紹了C語(yǔ)言的函數(shù)棧幀,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助,希望能夠給你帶來(lái)幫助
    2021-11-11
  • C語(yǔ)言printf詳細(xì)解析

    C語(yǔ)言printf詳細(xì)解析

    C中格式字符串printf()的一般形式為: %[標(biāo)志][輸出最小寬度][.精度][長(zhǎng)度]類(lèi)型, 其中方括號(hào)[]中的項(xiàng)為可選項(xiàng)。各項(xiàng)的意義介紹如下
    2013-09-09
  • DSP中浮點(diǎn)轉(zhuǎn)定點(diǎn)運(yùn)算--浮點(diǎn)數(shù)的存儲(chǔ)格式

    DSP中浮點(diǎn)轉(zhuǎn)定點(diǎn)運(yùn)算--浮點(diǎn)數(shù)的存儲(chǔ)格式

    本文主要介紹DSP中浮點(diǎn)數(shù)的存儲(chǔ)格式,很值得學(xué)習(xí)一下,需要的朋友可以參考一下。
    2016-06-06
  • C++超詳細(xì)梳理IO流操作

    C++超詳細(xì)梳理IO流操作

    當(dāng)程序與外界進(jìn)行信息交換時(shí),存在兩個(gè)對(duì)象,一個(gè)是程序中的對(duì)象,另一個(gè)是文件對(duì)象。流是信息流動(dòng)的一種抽象,它負(fù)責(zé)在數(shù)據(jù)的生產(chǎn)者和數(shù)據(jù)的消費(fèi)者之間建立聯(lián)系,并管理數(shù)據(jù)的流動(dòng)
    2022-07-07
  • 二叉搜索樹(shù)源碼分享

    二叉搜索樹(shù)源碼分享

    這篇文章主要介紹了二叉搜索樹(shù)源碼,需要的朋友可以參考下
    2014-04-04
  • C語(yǔ)言也有封裝,繼承和多態(tài)你知道嗎

    C語(yǔ)言也有封裝,繼承和多態(tài)你知道嗎

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言封裝,繼承,多態(tài),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2022-03-03

最新評(píng)論