class Solution {
public:
vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
}
};
面试题 17.17. 多次搜索
给定一个较长字符串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) <= 10000 <= len(smalls[i]) <= 1000smalls的总字符数不会超过 100000。smalls中没有重复字符串。原站题解
golang 解法, 执行用时: 76 ms, 内存消耗: 26.9 MB, 提交时间: 2022-08-26 14:36:47
type Trie struct {
children [26]*Trie
idx int
}
func newTrie() *Trie {
return &Trie{idx: -1}
}
func (this *Trie) insert(word string, idx int) {
node := this
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = newTrie()
}
node = node.children[idx]
}
node.idx = idx
}
func (this *Trie) search(word string) []int {
node := this
var res []int
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
return res
}
node = node.children[idx]
if node.idx != -1 {
res = append(res, node.idx)
}
}
return res
}
func multiSearch(big string, smalls []string) [][]int {
tree := newTrie()
for i, s := range smalls {
tree.insert(s, i)
}
n := len(smalls)
ans := make([][]int, n)
for i := range big {
s := big[i:]
t := tree.search(s)
for _, idx := range t {
ans[idx] = append(ans[idx], i)
}
}
return ans
}
python3 解法, 执行用时: 524 ms, 内存消耗: 44.8 MB, 提交时间: 2022-08-26 14:36:02
class Trie:
"""
前缀树
"""
def __init__(self):
self.idx = -1
self.children = [None] * 26
def insert(self, word, i):
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.idx = i
def search(self, word):
res = []
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return res
node = node.children[idx]
if node.idx != -1:
res.append(node.idx)
return res
class Solution:
def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
tree = Trie()
for i, s in enumerate(smalls):
tree.insert(s, i)
n = len(smalls)
ans = [[] for _ in range(n)]
for i in range(len(big)):
s = big[i:]
for idx in tree.search(s):
ans[idx].append(i)
return ans