648. 单词替换

原题链接：648. 单词替换

 

solution:

        哈希表存储前缀，暴力算法进行比较，O(n^2)

class Solution {
public:
    unordered_map<string, int> dict;    //存储单词前缀
    string replaceWords(vector<string>& dictionary, string sentence) {
        string res; //返回值
        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;
    }

    //字符串分割函数
    vector<string> split(string word, char t) {
        vector<string> res; //返回值
        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树 

const int N = 1e5 + 10;
class Solution {
public:
    int son[N][26], cnt[N], idx;    //建立字典树

    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]++;   //以p结尾的单词+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(!son[p][u]) break;   //如果不存在前缀则,break
            p = son[p][u];
        }
        return word;
    }

//字符串分割函数
    vector<string> split(string word, char t) {
        vector<string> res; //返回值
        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); //建立字典树
        vector<string> words = split(sentence, ' ');
        string res; //定义返回值
        for(int i = 0;i < words.size();i++) {
            string tmp = find(words[i]);
            res += tmp;
            if(i != words.size() - 1) res += ' ';
        }
        return res;
    }

};