Open azl397985856 opened 6 months ago
class Trie:
def __init__(self, words):
self.d = {}
for i in range(len(words)):
tree = self.d
for char in words[i]:
if char not in tree:
tree[char] = {}
tree = tree[char]
tree['end'] = i
def search(self, s):
tree = self.d
res = []
for char in s:
if char not in tree:
return res
tree = tree[char]
if 'end' in tree:
res.append(tree['end'])
return res
class Solution:
def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
trie = Trie(smalls)
res = [[] for _ in range(len(smalls))]
for i in range(len(big)):
tmp = trie.search(big[i:])
for idx in tmp:
res[idx].append(i)
return res
class Solution(object):
def multiSearch(self, big, smalls):
"""
:type big: str
:type smalls: List[str]
:rtype: List[List[int]]
"""
res = []
for small in smalls:
indices = []
tlen = len(small)
if tlen > 0:
for i in range(len(big)-tlen+1):
if big[i:i+tlen] == small:
indices.append(i)
res.append(indices)
return res
time complexity: O(n^2)
参考题解
public int[][] multiSearch(String big, String[] smalls) {
int n = smalls.length;
//首先创建一个res 的2d array
int[][] res = new int[n][];
// cur来记录找到的位置
List<Integer> cur = new ArrayList<>();
for (int i = 0; i < smalls.length; i++) {
String small = smalls[i];
if (small.length() == 0) {
res[i] = new int[]{};
continue;
}
//每一次从startIdx开始找
int startIdx = 0;
while (true) {
// idx是big里面first occur small的index
int idx = big.indexOf(small, startIdx);
//如果== -1 说明之后都没有small了, 退出while loop
if (idx == -1)
break;
//or把找到的index放入cur的array list里面
cur.add(idx);
//更新start index
startIdx = idx + 1;
}
//将cur复制到res[i][j]里面
res[i] = new int[cur.size()];
for (int j = 0; j < res[i].length; j++)
res[i][j] = cur.get(j);
cur.clear();
}
return res;
}
class Solution {
public:
struct Trie{
int smallIndex;
Trie* next[26];
Trie(){
smallIndex=-1;
memset(next,0,sizeof(next));
}
};
vector<vector<int>> res;
Trie* root=new Trie();
void insert(string s,int s_index){
Trie* node=root;
for(auto ch:s){
if(node->next[ch-'a']==NULL){
node->next[ch-'a']=new Trie();
}
node=node->next[ch-'a'];
}
node->smallIndex=s_index;
}
void search(string subBig,int index){
Trie* node=root;
for(auto ch:subBig){
if(node->next[ch-'a']==NULL) return;
node=node->next[ch-'a'];
if(node->smallIndex!=-1){
res[node->smallIndex].push_back(index);
}
}
}
vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
res.resize(smalls.size());
for(int i=0;i<smalls.size();i++){
insert(smalls[i],i);
}
for(int i=0;i<big.size();i++){
string subBig=big.substr(i);
search(subBig,i);
}
return res;
}
};
function TreeNode(val) { this.val = val || null this.children = {} }
/**
@return {number[][]} */ var multiSearch = function (big, smalls) { const res = smalls.map(() => []) if (!big) { return res } let Tree = new TreeNode() let now; smalls.forEach((small, index) => { now = Tree; for (let i = 0; i < small.length; i++) { if (!now.children[small[i]]) { now.children[small[i]] = new TreeNode(small[i]) } now = now.children[small[i]] } now.children['last'] = index })
for (let i = 0; i < big.length; i++) { let now = Tree; for (let j = i; j < big.length; j++) { if (!now.children[big[j]]) { break } now = now.children[big[j]] if (now.children.last !== undefined) { res[now.children.last].push(i) } } } return res };
class Solution {
public int[][] multiSearch(String big, String[] smalls) {
if (smalls == null || smalls.length == 0) {
return new int[][]{};
}
int length = smalls.length;
int[][] res = new int[length][];
for (int i = 0; i < length; i++) {
if ("".equals(smalls[i])) {
res[i] = new int[]{};
continue;
}
List<Integer> list = new ArrayList<>();
int index = 0;
while (big.indexOf(smalls[i], index) != -1) {
int position = big.indexOf(smalls[i], index);
list.add(position);
//从当前匹配到的位置的下一个位置开始继续匹配
index = position + 1;
}
res[i] = list.stream().mapToInt(Integer::intValue).toArray();
}
return res;
}
}
class Trie:
def __init__(self, words):
self.d = {} # Trie 树的根节点
for word in words:
t = self.d
for w in word:
if w not in t:
t[w] = {} # 创建新的 TrieNode 节点
t = t[w]
t['end'] = word # 在单词的末尾标记 'end'
def search(self, s):
t = self.d
res = []
for w in s:
if w not in t:
break
t = t[w]
if 'end' in t:
res.append(t['end']) # 如果到达单词末尾,则将单词添加到结果列表
return res
class Solution:
def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
trie = Trie(smalls) # 创建 Trie 对象并初始化
hit = collections.defaultdict(list) # 用于存储每个小字符串的匹配位置
for i in range(len(big)):
matchs = trie.search(big[i:]) # 在 big 中查找以 big[i:] 为前缀的所有小字符串
for word in matchs:
hit[word].append(i) # 记录匹配位置
res = []
for word in smalls:
res.append(hit[word]) # 将每个小字符串的匹配位置列表添加到结果列表
return res
面试题 17.17 多次搜索
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/multi-search-lcci
前置知识
题目描述
示例:
输入: 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 中没有重复字符串。 所有出现的字符均为英文小写字母。