[LeetCode] 648. 单词替换

[Animenzzzz]

题目描述：

在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1:

输入: dict(词典) = ["cat", "bat", "rat"]
sentence(句子) = "the cattle was rattled by the battery"
输出: "the cat was rat by the bat"

注:

输入只包含小写字母。
1 <= 字典单词数 <=1000
1 <=  句中词语数 <= 1000
1 <= 词根长度 <= 100
1 <= 句中词语长度 <= 1000

解题思路：这题使用字典树。首先使用字典创建好字典树，然后一次遍历，把句子分割成一个个单词放进singleWords中。使用resultword暂存检索到的前缀，由于需要匹配最短词根，跳出遍历单个单词的条件：1.当前字母的节点为空 2.前缀单词串已经结束（isWordEnd == true）。然后需要判断，
1.如果resultword为空，说明第一个字母都没有匹配，直接把整个单词（word）放进resultWords
2.如果resultword不为空，而且isWordEnd == true，说明遍历完一个前缀串，把resultword放进resultWords
3.如果resultword不为空，而且isWordEnd == false，说明这个单词前面几个字母在前缀中，但是后面有字母不在前缀中，则直接把word存进resultWords
最后，遍历resultWords拼接好字符串返回

C++解题：

class TrieNode{
public:
    TrieNode *child[26];
    bool isWordEnd;
    TrieNode(): isWordEnd(false){
        for (int i = 0; i < 26; i++) child[i] = nullptr;
    }
};

class Solution {
public:
    string replaceWords(vector<string>& dict, string sentence) {
        vector<string> singleWords;
        vector<string> resultWords;
        string result;
        for (int i = 0; i < sentence.size(); i++)
        {
            string tmp;
            while (i < sentence.size() && sentence[i] != ' ')
            {
                tmp = tmp + sentence[i];
                i++;
            }
            singleWords.push_back(tmp);
        }
        for (int i = 0; i < dict.size(); i++) addWord(dict[i],root);
        for (int i = 0; i < singleWords.size(); i++)
        {
            string word = singleWords[i];
            string resultword;
            TrieNode *p = root;
            for (int j = 0; j < word.size(); j++)
            {
                if(!p->child[word[j] - 'a'] || p->isWordEnd)  break;
                else resultword = resultword+word[j];
                p = p->child[word[j]-'a'];
            }
            if(!resultword.size()) resultWords.push_back(word);
            else if(p->isWordEnd) resultWords.push_back(resultword);
            else resultWords.push_back(word);
        }
        for (int i = 0; i < resultWords.size(); i++) result = result + " " + resultWords[i];
        result.erase(0,1);
        return result;
    }
    void addWord(string word,TrieNode *root){
        TrieNode *p = root;
        for (int i = 0; i < word.size(); i++)
        {
            int index = word[i] - 'a';
            if(!p->child[index]) p->child[index] = new TrieNode();
            p = p->child[index];
        }
        p->isWordEnd = true;
    }
private:
    TrieNode *root = new TrieNode();
};