【Day 75 】2024-01-29 - 面试题 17.17 多次搜索

[azl397985856]

面试题 17.17 多次搜索

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/multi-search-lcci

前置知识

• 字符串匹配
• Trie

题目描述

给定一个较长字符串 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 中没有重复字符串。
所有出现的字符均为英文小写字母。

[smallppgirl]

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

[Chloe-C11]

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)

[Junru281]

参考题解

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;
}

[snmyj]

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;
    }
};

[adfvcdxv]

function TreeNode(val) {
this.val = val || null
this.children = {}
}

/**

• @param {string} big

• @param {string[]} smalls

• @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
  };

[larscheng]

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;
    }
}

[Danielyan86]

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