题目描述

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

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

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

样例

输入: 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

算法

(Trie树) $O(S1 + S2)$

1. 将字典中所有单词建立 Trie树（前缀树），然后在单词的末尾记录标记为单词结束。此处在建树的过程中，若发现某个单词是另一个单词的前缀，则较长的单词可以不再继续往下建。
2. 查询时，按照字典树匹配句中的单词，若发现某个前缀匹配上了句子单词的前缀，则按照题意将之后的后缀去掉。

时间复杂度

• Trie树的建立和查询都是线性时间复杂度，$S1$ 是字典的字母数，$S2$ 是句子的字母数，故总时间复杂度为 $O(S1 + S2)$。

C++ 代码

class Solution {
public:
    struct Node {
        Node *nxt[26];
        bool end_of_root;
        Node() {
            memset(nxt, NULL, sizeof(nxt));
            end_of_root = false;
        }
    };
    Node *rt = new Node();

    void insert(const string &s) {
        int l = s.length();
        Node *p = rt;
        for (int i = 0; i < l; i++) {
            if (p -> nxt[s[i] - 'a'] == NULL)
                p -> nxt[s[i] - 'a'] = new Node();
            p = p -> nxt[s[i] - 'a'];
            if (p -> end_of_root == true)
                return;
        }
        p -> end_of_root = true;
    }

    string replace(const string &s, int st, int ed) {
        Node *p = rt;
        for (int i = st; i <= ed; i++) {
            if (p -> nxt[s[i] - 'a'] == NULL)
                break;
            p = p -> nxt[s[i] - 'a'];
            if (p -> end_of_root == true)
                return s.substr(st, i - st + 1);
        }
        return s.substr(st, ed - st + 1);
    }

    string replaceWords(vector<string>& dict, string sentence) {
        for (string &s : dict)
            insert(s);

        string ans = "";
        int l = sentence.length(), last = 0;
        for (int i = 0; i < l; i++)
            if (sentence[i] == ' ') {
                ans += replace(sentence, last, i - 1) + " ";
                last = i + 1;
            }

        return ans + replace(sentence, last, l - 1);
    }
};