648.单词替换

链接：648.单词替换
难度：Medium
标签：字典树、数组、哈希表、字符串
简介：现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

题解 1 - cpp

• 编辑时间：2022-07-07
• 执行用时：68ms
• 内存消耗：54.5MB
• 编程语言：cpp
• 解法介绍：字典树。

class TrieNode {
   public:
    TrieNode **children;
    bool end;
    TrieNode() {
        children = (TrieNode **)malloc(sizeof(TrieNode *) * 26);
        for (int i = 0; i < 26; i++) children[i] = nullptr;
        end = false;
    }
    void insert(string str) {
        TrieNode *node = this;
        for (int i = 0; i < str.size(); i++) {
            int idx = str[i] - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
            if (i == str.size() - 1) node->end = true;
        }
    }
    string find(string str) {
        TrieNode *node = this;
        string ans = "", tmp = "";
        for (int i = 0; i < str.size(); i++) {
            int idx = str[i] - 'a';
            tmp += str[i];
            if (!node->children[idx]) return ans;
            node = node->children[idx];
            if (node->end) return tmp;
        }
        return ans;
    }
};
class Solution {
   public:
    TrieNode *root = new TrieNode();
    string replaceWords(vector<string> &dictionary, string sentence) {
        vector<string> list;
        string ans = "";
        for (auto &str : dictionary) root->insert(str);
        for (auto &str : split(sentence)) {
            string res = root->find(str);
            if (res == "")
                list.push_back(str);
            else
                list.push_back(res);
        }
        for (int i = 0; i < list.size(); i++) {
            if (i != 0) ans += " ";
            ans += list[i];
        }
        return ans;
    }
    vector<string> split(string &str) {
        vector<string> ans;
        string tmp = "";
        for (auto &ch : str) {
            if (ch == ' ') {
                ans.push_back(tmp);
                tmp = "";
            } else
                tmp += ch;
        }
        ans.push_back(tmp);
        return ans;
    }
};