leetcode 多次搜索

题目

多次搜索

暴力解法

我这里的暴力解法，用了两边for循环 + hash，虽然过了但是时间复杂度惨不忍睹。。。

惨不忍睹的时间

具体方法为，一遍hash表把所有的smalls串存起来，然后两边for循环构造big的所有子串再到hash表里判断是否存在。

代码

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        unordered_map<string, int> mp(smalls.size());
        for (int i = 0; i < smalls.size(); i++) {
            mp[smalls[i]] = i;
        }
        
        vector<vector<int>> res(smalls.size(), vector<int>());
        for (int l = 1; l <= big.size(); l++) {
            for (int i = 0; i + l - 1 < big.size(); i++) {
                string s = big.substr(i, l);
                if (mp.count(s)) {
                    res[mp[s]].push_back(i);
                }
            }
        }

        return res;
    }
};

字典树

先说说这道题为啥可以使用字典树求解。字典树又叫前缀树，这个前缀两个字很关键。在上面的暴力解法中，我们之所以需要两遍for循环，就是因为我们需要完全匹配，每次求解只能找到一个解，因为我们是通过完全匹配一个子串的方法。而前缀树就不一样，一个相同的前缀可以对应众多的字符串，所以我们不需要两遍for循环来完全匹配子串了，只需要一遍for循环来匹配前缀就行了。

代码

struct MyTreeNode{
    int start_id;
    MyTreeNode* children[26];
    MyTreeNode(int id = -1) {
        start_id = id;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class Solution {
private:
    MyTreeNode* root[26];
    vector<vector<int>> res;

    void dfs_for_search_word(int k, string& str, MyTreeNode* &root, int index) {
        if (root == nullptr) {
            return;
        }
        if (root->start_id != -1) {
            res[root->start_id].push_back(index);
        }
        if (k + 1 < str.size()) {
            dfs_for_search_word(k + 1, str, root->children[str[k + 1] - 'a'], index);
        }
    }

    void dfs_for_create_tree(int k, string& str, MyTreeNode* &root, int id) {
        if (root == nullptr) {
            root = new MyTreeNode();
        }
        if (k == str.size() - 1) {
            root->start_id = id;
        }
        if (k + 1 < str.size()) {
            dfs_for_create_tree(k + 1, str, root->children[str[k + 1] - 'a'], id);
        }
    }

public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        res = vector<vector<int>>(smalls.size(), vector<int>());

        for (int i = 0; i < smalls.size(); i++) {
            if (smalls[i].empty()){
                continue;
            }
            dfs_for_create_tree(0, smalls[i], root[smalls[i][0] - 'a'], i);
        }

        for (int i = 0; i < big.size(); i++) {
            string str = big.substr(i, big.size() - i);
            dfs_for_search_word(0, str, root[str[0] - 'a'], i);
        }

        return res;
    }
};