LeetCode648.使用Trie树实现单词替换

问题描述

在英语语言学中，存在一个称为词根（root）的概念，它能够与其它词汇组合形成新的、更长的词汇——这类新形成的词汇被定义为继承词（successor）。例如，词根'an'与单词'other'结合，可以生成新词'another'。

本题提供了一个词根列表和一个句子。目标是将句子中所有的继承词替换为其对应的词根。若一个继承词可由多个词根构成，则选择最短的那个词根进行替换。最终需要返回经过替换后的句子。

示例输入: 词根列表 = ["cat", "bat", "rat"]
句子 = "the cattle was rattled by the battery"
期望输出: "the cat was rat by the bat"
限制条件:
输入仅包含小写字母。
词根列表的长度范围为1至1000。
句子中的单词数量不超过1000个。
单个词根的最大长度为100。
句子中单词的最大长度为1000。

Trie树解决方案

此问题可以通过构建Trie树来高效解决。首先，将所有的词根插入到Trie树中；接着，对于句子中的每一个单词，检查其所有可能的前缀是否存在于Trie树中，如果存在，则使用该前缀（即词根）替换原单词。

以下是C++实现代码示例：

class TrieNode {
    public:
        char value;
        bool isWord;
        TrieNode* children[26];
        TrieNode(char val): value(val), isWord(false) {
            memset(children, 0, sizeof(children));
        }
};

class Trie {
    private:
        TrieNode* root;
    public:
        Trie() { root = new TrieNode('/0'); }
        ~Trie() { destroy(root); }
        void destroy(TrieNode* node) {
            for (int i = 0; i <26; ++i) {
                if (node->children[i]) destroy(node->children[i]);
            }
            delete node;
        }
        void insert(const std::string& word) {
            TrieNode* current = root;
            for (char c : word) {
                if (!current->children[c - 'a']) {
                    current->children[c - 'a'] = new TrieNode(c);
                }
                current = current->children[c - 'a'];
            }
            current->isWord = true;
        }
        std::string searchPrefix(const std::string& word) {
            TrieNode* current = root;
            std::string prefix;
            for (char c : word) {
                if (!current->children[c - 'a']) return "";
                current = current->children[c - 'a'];
                prefix += c;
                if (current->isWord) return prefix;
            }
            return "";
        }
};

class Solution {
    public:
        std::string replaceWords(std::vector& dictionary, std::string sentence) {
            Trie trie;
            for (const std::string& root : dictionary) {
                trie.insert(root);
            }
            std::stringstream ss(sentence);
            std::string word, result;
            while (ss >> word) {
                std::string prefix = trie.searchPrefix(word);
                result += (prefix.empty() ? word : prefix) + " ";
            }
            if (!result.empty()) result.pop_back();
            return result;
        }
};