多次搜索
- 难度:Medium
- 题目链接:https://leetcode-cn.com/problems/multi-search-lcci/
题目描述
给定一个较长字符串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
中没有重复字符串。 - 所有出现的字符均为英文小写字母。
解法一:暴力搜索
class Solution {
public:
vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
vector<vector<int>> ret;
for(string& s: smalls){
vector<int> positions;
if(s.empty()){
ret.push_back(::move(positions));
continue;
}
int start = 0;
int i = big.find(s, start);
while(i != string::npos){
positions.push_back(i);
start = i + 1;
i = big.find(s, start);
}
ret.push_back(::move(positions));
}
return ret;
}
};
解法二:Trie
把所有短单词都存储在 Trie 中。然后使用 big[i:]
去 Trie 树中寻找 big[i:]
的前缀。