648. Replace Words

https://leetcode.com/problems/replace-words/description/
Solution 1. Trie search
class Solution {
#define NAL 26
    struct trieNode {
        trieNode* child[NAL] = {nullptr};
        bool isEnd = false;
    };
    void insert(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->child[key[i]-'a'] == nullptr) {
                p->child[key[i]-'a'] = new trieNode;
            }
            p = p->child[key[i]-'a'];
            if(p->isEnd == true) return;
        }
        p->isEnd = true;
    }
    int search(trieNode*root, string& key) {
        trieNode* p = root;
        for(int i=0; i<key.size(); i++) {
            if(p->isEnd == true){ return i; }
            if(p->child[key[i]-'a'] == nullptr) return 0;
            p = p->child[key[i]-'a'];
        }
        return 0;
    }
public:
    string replaceWords(vector<string>& dict, string sentence) {
        trieNode* root = new trieNode;
        for(string &s : dict) {
            insert(root, s);
        }
        string res = "", word;
        istringstream iss(sentence);
        while(iss>>word) {
            cout<<endl;
            int len = search(root, word);
            if(len) res += " " + word.substr(0,len);
            else res += " " + word;
        }
        return res.substr(1);
    }
};


Solution 2. (166 ms)
    string replaceWords(vector<string>& dict, string sentence) {
        istringstream iss(sentence);
        string word;
        string res;
        unordered_set<string> st;
        for(auto &s : dict) st.insert(s);
        while(iss>>word) {
            int i;
            for(i=0; i<word.size(); i++) {
                if(st.count(word.substr(0,i+1))) break;
            }
            if(i!=word.size()) res += " " + word.substr(0,i+1);
            else res += " " + word;
        }
        return res.substr(1);
    }