1. 題目

在英語(yǔ)中，我們有一個(gè)叫做 詞根(root)的概念，它可以跟著其他一些詞組成另一個(gè)較長(zhǎng)的單詞——我們稱(chēng)這個(gè)詞為 繼承詞(successor)。例如，詞根an，跟隨著單詞 other(其他)，可以形成新的單詞 another(另一個(gè))。

現(xiàn)在，給定一個(gè)由許多詞根組成的詞典和一個(gè)句子。你需要將句子中的所有繼承詞用詞根替換掉。如果繼承詞有許多可以形成它的詞根，則用最短的詞根替換它。

你需要輸出替換之后的句子。

輸入: dict(詞典) = ["cat", "bat", "rat"] sentence(句子) = "the cattle was rattled by the battery" 輸出: "the cat was rat by the bat"注: 輸入只包含小寫(xiě)字母。 1 <= 字典單詞數(shù) <=1000 1 <= 句中詞語(yǔ)數(shù) <= 1000 1 <= 詞根長(zhǎng)度 <= 100 1 <= 句中詞語(yǔ)長(zhǎng)度 <= 1000

2. Trie解題

參考：Trie樹(shù)

• 先將單詞插入Trie樹(shù)
• 然后依次查詢(xún)每個(gè)單詞的各前綴是否在Trie中，進(jìn)行替換

class TrieNode//節(jié)點(diǎn) { public:char ch;TrieNode *next[26];bool isEnd;TrieNode(char c = '/'):ch(c),isEnd(false) {memset(next, 0, sizeof(TrieNode*)*26);} }; class Trie//Trie樹(shù) { public:TrieNode *root;Trie(){root = new TrieNode();}~Trie()//析構(gòu)釋放內(nèi)存{destroy(root);}void destroy(TrieNode *root){if(root == NULL)return;for(int i = 0; i < 26; i++)destroy(root->next[i]);delete root;}void insert(string str)//插入單詞{TrieNode *cur = root;for(char s:str){if(cur->next[s-'a'] == NULL)cur->next[s-'a'] = new TrieNode(s-'a');cur = cur->next[s-'a'];}cur->isEnd = true;} }; class Solution {Trie tree; public:string replaceWords(vector<string>& dict, string sentence) {for(string s:dict)tree.insert(s);string word, ans, prefix;TrieNode *cur = tree.root;istringstream in(sentence);int i, chIdx;while(in >> word){cur = tree.root;prefix = "";for(i = 0; i < word.size(); ++i){chIdx = word[i]-'a';if(cur->next[chIdx] == NULL){ans += word;break;}else{prefix.push_back(word[i]);if(cur->next[chIdx]->isEnd){ans += prefix;break;}if(i == word.size()-1)//最后一個(gè)字符特殊處理ans += prefix;}cur = cur->next[chIdx];}ans.push_back(' ');}ans.pop_back();//刪除空格return ans;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 648. 单词替换（Trie树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。