程序员面试金典 - 面试题 17.17. 多次搜索（Trie树）

文章目录

• • 1. 题目
  • 2. 解题
  • • 2.1 暴力超时
    • 2.2 Trie树

1. 题目

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。
输出smalls中的字符串在big里出现的所有位置positions，其中 positions[i] 为 smalls[i] 出现的所有位置。

示例： 输入： big = "mississippi" smalls = ["is","ppi","hi","sis","i","ssippi"] 输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]提示： 0 <= len(big) <= 1000 0 <= len(smalls[i]) <= 1000 smalls的总字符数不会超过 100000。 你可以认为smalls中没有重复字符串。 所有出现的字符均为英文小写字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multi-search-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 暴力超时

超时例子

class Solution { public:vector<vector<int>> multiSearch(string big, vector<string>& smalls) {unordered_map<char,vector<int>> m;int i, j, n = smalls.size();bool found;vector<vector<int>> ans(n);for(i = 0; i < big.size(); ++i)m[big[i]].push_back(i);//每个字符开始的位置for(i = 0; i < n; ++i){if(smalls[i].empty())continue;for(auto idx : m[smalls[i][0]])//每个small单词开始的字符在big里的位置{found = true;if(big.size()-idx < smalls[i].size())break;for(j = 0; j < smalls[i].size(); ++j){ //对big中每个开始的位置开始向后查找smallif(big[idx+j] != smalls[i][j]){found = false;break;}}if(found)ans[i].push_back(idx);}}return ans;} };

2.2 Trie树

• 将 small 全部插入 trie 树
• 遍历 big 的每个位置，并从 big 该位置开始在 trie 中查找

class trie { public:bool isEnd = false;trie* next[26] = {NULL};void insert(string& s){trie *cur = this;for(int i = 0; i < s.size(); ++i){if(!cur->next[s[i]-'a'])cur->next[s[i]-'a'] = new trie();cur = cur->next[s[i]-'a'];}cur->isEnd = true;} }; class Solution { public:vector<vector<int>> multiSearch(string big, vector<string>& smalls) {trie* t = new trie();unordered_map<string,int> m;int i, j, n = smalls.size();bool found;vector<vector<int>> ans(n);for(i = 0; i < n; ++i)m[smalls[i]] = i;for(i = 0; i < n; ++i)t->insert(smalls[i]);string s;trie* cur;for(i = 0; i < big.size(); ++i){s = "";cur = t;for(j = i; j < big.size(); ++j){if(!cur->next[big[j]-'a'])break;s += big[j];cur = cur->next[big[j]-'a'];if(cur->isEnd)ans[m[s]].push_back(i);}}return ans;} };

336 ms 108.7 MB

总结

以上是生活随笔为你收集整理的程序员面试金典 - 面试题 17.17. 多次搜索（Trie树）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。