648.单词替换 (Medium)*

class TrieNode {
public:
    bool flag;
    unordered_map<char, TrieNode*> next;
    TrieNode() : flag(false) {}
};

class Solution {
private:
    TrieNode* root;
public:
    Solution() {
        root = new TrieNode();
    }
    string replaceWords(vector<string>& dict, string s) {
        if(s == "") {
            return "";
        }
        auto cur = root;
        // 构造字典树
        for(auto& word : dict) {
            cur = root;
            for(auto& c : word) {
                if(!cur->next.count(c)) {
                    cur->next[c] = new TrieNode();
                }
                cur = cur->next[c];
            }
            cur->flag = true;
        }
        string res;
        int start = 0;
        int end = 0;
        int len = s.length();
        for(int i = 0; i < len; i++) {
            if(s[i] == ' ') {
                continue;
            }
            cur = root;
            start = i;
            while(i < len && s[i] != ' ') {
                // 匹配词根，取最短词根
                if(cur->flag || !cur->next.count(s[i])) {
                    break;
                }
                cur = cur->next[s[i]];
                i++;
            }
            end = i;
            while(i < len && s[i] != ' ') {
                i++;
            }
            // 没找到词根
            if(!cur->flag) {
                end = i;
            }
            res += s.substr(start, end - start) + " ";
        }
        res.pop_back();
        return res;
    }
};

class TrieNode {
public:
    bool flag;
    vector<TrieNode*> next;
    TrieNode() : flag(false), next(vector<TrieNode*>(26, nullptr)) {}
};

class Solution {
private:
    TrieNode* root;
public:
    Solution() {
        root = new TrieNode();
    }
    string replaceWords(vector<string>& dict, string s) {
        if(s == "") {
            return "";
        }
        auto cur = root;
        // 构造字典树
        for(auto& word : dict) {
            cur = root;
            for(auto& c : word) {
                if(cur->next[c - 'a'] == nullptr) {
                    cur->next[c - 'a'] = new TrieNode();
                }
                cur = cur->next[c - 'a'];
            }
            cur->flag = true;
        }
        string res;
        int start = 0;
        int end = 0;
        int len = s.length();
        for(int i = 0; i < len; i++) {
            if(s[i] == ' ') {
                continue;
            }
            cur = root;
            start = i;
            while(i < len && s[i] != ' ') {
                if(cur->flag || cur->next[s[i] - 'a'] == nullptr) {
                    break;
                }
                cur = cur->next[s[i] - 'a'];
                i++;
            }
            end = i;
            while(i < len && s[i] != ' ') {
                i++;
            }
            // 没找到词根
            if(!cur->flag) {
                end = i;
            }
            res += s.substr(start, end - start) + " ";
        }
        res.pop_back();
        return res;
    }
};