C++實(shí)現(xiàn)LeetCode(648.替換單詞)
[LeetCode] 648.Replace Words 替換單詞
In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:
Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Note:
- The input will only have lower-case letters.
- 1 <= dict words number <= 1000
- 1 <= sentence words number <= 1000
- 1 <= root length <= 100
- 1 <= sentence words length <= 1000
這道題給了我們一個(gè)前綴字典,又給了一個(gè)句子,讓我們將句子中較長的單詞換成其前綴(如果在前綴字典中存在的話)。我們對于句子中的一個(gè)長單詞如何找前綴呢,是不是可以根據(jù)第一個(gè)字母來快速定位呢,比如cattle這個(gè)單詞的首字母是c,那么我們在前綴字典中找所有開頭是c的前綴,為了方便查找,我們將首字母相同的前綴都放到同一個(gè)數(shù)組中,總共需要26個(gè)數(shù)組,所以我們可以定義一個(gè)二維數(shù)組來裝這些前綴。還有,我們希望短前綴在長前綴的前面,因?yàn)轭}目中要求用最短的前綴來替換單詞,所以我們可以先按單詞的長度來給所有的前綴排序,然后再依次加入對應(yīng)的數(shù)組中,這樣就可以保證短的前綴在前面。
下面我們就要來遍歷句子中的每一個(gè)單詞了,由于C++中沒有split函數(shù),所以我們就采用字符串流來提取每一個(gè)單詞,對于遍歷到的單詞,我們根據(jù)其首字母查找對應(yīng)數(shù)組中所有以該首字母開始的前綴,然后直接用substr函數(shù)來提取單詞中和前綴長度相同的子字符串來跟前綴比較,如果二者相等,說明可以用前綴來替換單詞,然后break掉for循環(huán)。別忘了單詞之前還要加上空格,參見代碼如下:
解法一:
class Solution { public: string replaceWords(vector<string>& dict, string sentence) { string res = "", t = ""; vector<vector<string>> v(26); istringstream is(sentence); sort(dict.begin(), dict.end(), [](string &a, string &b) {return a.size() < b.size();}); for (string word : dict) { v[word[0] - 'a'].push_back(word); } while (is >> t) { for (string word : v[t[0] - 'a']) { if (t.substr(0, word.size()) == word) { t = word; break; } } res += t + " "; } res.pop_back(); return res; } };
你以為想出了上面的解法,這道題就算做完了?? Naive! ! ! 這道題最好的解法其實(shí)是用前綴樹(Trie / Prefix Tree)來做,關(guān)于前綴樹使用之前有一道很好的入門題Implement Trie (Prefix Tree)。了解了前綴樹的原理機(jī)制,那么我們就可以發(fā)現(xiàn)這道題其實(shí)很適合前綴樹的特點(diǎn)。我們要做的就是把所有的前綴都放到前綴樹里面,而且在前綴的最后一個(gè)結(jié)點(diǎn)的地方將標(biāo)示isWord設(shè)為true,表示從根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)是一個(gè)前綴,然后我們在遍歷單詞中的每一個(gè)字母,我們都在前綴樹查找,如果當(dāng)前字母對應(yīng)的結(jié)點(diǎn)的表示isWord是true,我們就返回這個(gè)前綴,如果當(dāng)前字母對應(yīng)的結(jié)點(diǎn)在前綴樹中不存在,我們就返回原單詞,這樣就能完美的解決問題了。所以啊,以后遇到了有關(guān)前綴或者類似的問題,一定不要忘了前綴樹這個(gè)神器喲~
解法二:
class Solution { public: class TrieNode { public: bool isWord; TrieNode *child[26]; TrieNode(): isWord(false) { for (auto &a : child) a = NULL; } }; string replaceWords(vector<string>& dict, string sentence) { string res = "", t = ""; istringstream is(sentence); TrieNode *root = new TrieNode(); for (string word : dict) { insert(root, word); } while (is >> t) { if (!res.empty()) res += " "; res += findPrefix(root, t); } return res; } void insert(TrieNode* node, string word) { for (char c : word) { if (!node->child[c - 'a']) node->child[c - 'a'] = new TrieNode(); node = node->child[c - 'a']; } node->isWord = true; } string findPrefix(TrieNode* node, string word) { string cur = ""; for (char c : word) { if (!node->child[c - 'a']) break; cur.push_back(c); node = node->child[c - 'a']; if (node->isWord) return cur; } return word; } };
類似題目:
參考資料:
https://discuss.leetcode.com/topic/97203/trie-tree-concise-java-solution-easy-to-understand
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(648.替換單詞)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)替換單詞內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++析構(gòu)函數(shù)內(nèi)部工作機(jī)制詳解
析構(gòu)函數(shù)(Destructor)也是一種特殊的成員函數(shù),沒有返回值,不需要程序員顯式調(diào)用(程序員也沒法顯式調(diào)用),而是在銷毀對象時(shí)自動(dòng)執(zhí)行。構(gòu)造函數(shù)的名字和類名相同,而析構(gòu)函數(shù)的名字是在類名前面加一個(gè)~符號2023-02-02二叉樹中葉子節(jié)點(diǎn)的統(tǒng)計(jì)和樹高問題
今天小編就為大家分享一篇關(guān)于二叉樹中葉子節(jié)點(diǎn)的統(tǒng)計(jì)和樹高問題,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧2019-03-03C語言實(shí)現(xiàn)宿舍管理系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)宿舍管理系統(tǒng)課程設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03C語言中的狀態(tài)機(jī)設(shè)計(jì)深入講解
這篇文章主要給大家介紹了關(guān)于C語言狀態(tài)機(jī)設(shè)計(jì)的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11詳細(xì)分析C++ 數(shù)據(jù)封裝和數(shù)據(jù)抽象
這篇文章主要介紹了C++ 數(shù)據(jù)封裝和數(shù)據(jù)抽象的的相關(guān)資料,文中代碼非常詳細(xì),幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下2020-06-06