648. Word replacement

Original link ：648. Word substitution

 

solution:

        Hash table stores prefix , Violent algorithm for comparison ,O(n^2)

class Solution {
public:
    unordered_map<string, int> dict;    // Store word prefixes 
    string replaceWords(vector<string>& dictionary, string sentence) {
        string res; // Return value 
        for(auto &x : dictionary) dict[x]++;
        vector<string> words = split(sentence, ' ');

        for(auto &word : words) {
            for(int i = 0;i < word.size();i++) {
                string tmp = word.substr(0, i + 1);
                if(dict[tmp]) {
                    word = tmp;
                    break;
                }
            }
        }

        for(int i = 0;i < words.size();i++) {
            res += words[i];
            if(i != words.size() - 1) res += ' ';
        }
        return res;
    }

    // String splitting function 
    vector<string> split(string word, char t) {
        vector<string> res; // Return value 
        int n = word.size();
        for(int i = 0;i < n;i++) {
            int j = i;
            string item;
            while(j < n && word[j] != t) item += word[j++];
            i = j;
            res.push_back(item);
        }
        return res;
    }
};

        trie Trees  

const int N = 1e5 + 10;
class Solution {
public:
    int son[N][26], cnt[N], idx;    // Build a dictionary tree 

    void add(string word) {
        int p = 0;
        for(int i = 0;i < word.size();i++) {
            int u = word[i] - 'a';
            if(!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;   // With p Ending words +1
    }

    string find(string word) {
        int p = 0;
        for(int i = 0;i < word.size();i++) {
            int u = word[i] - 'a';
            if(cnt[p]) return word.substr(0, i);    // If prefix appears, replace 
            if(!son[p][u]) break;   // If no prefix exists then ,break
            p = son[p][u];
        }
        return word;
    }

// String splitting function 
    vector<string> split(string word, char t) {
        vector<string> res; // Return value 
        int n = word.size();
        for(int i = 0;i < n;i++) {
            int j = i;
            string item;
            while(j < n && word[j] != t) item += word[j++];
            i = j;
            res.push_back(item);
        }
        return res;
    }

    string replaceWords(vector<string>& dictionary, string sentence) {
        for(auto &word : dictionary) add(word); // Build a dictionary tree 
        vector<string> words = split(sentence, ' ');
        string res; // Define the return value 
        for(int i = 0;i < words.size();i++) {
            string tmp = find(words[i]);
            res += tmp;
            if(i != words.size() - 1) res += ' ';
        }
        return res;
    }

};