[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:

1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

這道題給了我們一個(gè)前綴字典，又給了一個(gè)句子，讓我們將句子中較長(zhǎng)的單詞換成其前綴(如果在前綴字典中存在的話)。我們對(duì)于句子中的一個(gè)長(zhǎng)單詞如何找前綴呢，是不是可以根據(jù)第一個(gè)字母來快速定位呢，比如cattle這個(gè)單詞的首字母是c，那么我們?cè)谇熬Y字典中找所有開頭是c的前綴，為了方便查找，我們將首字母相同的前綴都放到同一個(gè)數(shù)組中，總共需要26個(gè)數(shù)組，所以我們可以定義一個(gè)二維數(shù)組來裝這些前綴。還有，我們希望短前綴在長(zhǎng)前綴的前面，因?yàn)轭}目中要求用最短的前綴來替換單詞，所以我們可以先按單詞的長(zhǎng)度來給所有的前綴排序，然后再依次加入對(duì)應(yīng)的數(shù)組中，這樣就可以保證短的前綴在前面。

下面我們就要來遍歷句子中的每一個(gè)單詞了，由于C++中沒有split函數(shù)，所以我們就采用字符串流來提取每一個(gè)單詞，對(duì)于遍歷到的單詞，我們根據(jù)其首字母查找對(duì)應(yīng)數(shù)組中所有以該首字母開始的前綴，然后直接用substr函數(shù)來提取單詞中和前綴長(zhǎng)度相同的子字符串來跟前綴比較，如果二者相等，說明可以用前綴來替換單詞，然后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è)前綴，然后我們?cè)诒闅v單詞中的每一個(gè)字母，我們都在前綴樹查找，如果當(dāng)前字母對(duì)應(yīng)的結(jié)點(diǎn)的表示isWord是true，我們就返回這個(gè)前綴，如果當(dāng)前字母對(duì)應(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;
    }
};

類似題目：

Implement Trie (Prefix Tree)

參考資料：

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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論