C++實(shí)現(xiàn)LeetCode(676.實(shí)現(xiàn)神奇字典)
[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:
- You may assume that all the inputs are consist of lowercase letters a-z.
- For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
- 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)似題目:
參考資料:
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ù)問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02C++常用函數(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-02C++11?成員函數(shù)作為回調(diào)函數(shù)的使用方式
這篇文章主要介紹了C++11?成員函數(shù)作為回調(diào)函數(shù)的使用方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-11-11DSP中浮點(diǎn)轉(zhuǎn)定點(diǎn)運(yùn)算--浮點(diǎn)數(shù)的存儲(chǔ)格式
本文主要介紹DSP中浮點(diǎn)數(shù)的存儲(chǔ)格式,很值得學(xué)習(xí)一下,需要的朋友可以參考一下。2016-06-06