【Day 75 】2023-04-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 中没有重复字符串。 所有出现的字符均为英文小写字母。

[lp1506947671]

class Trie:
    def __init__(self, words):
        self.d = {}
        for word in words:
            t = self.d
            for w in word:
                if w not in t:
                    t[w] = {}
                t = t[w]
            t['end'] = word

    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)
        hit = collections.defaultdict(list)

        for i in range(len(big)):
            matchs = trie.search(big[i:])
            for word in matchs:
                hit[word].append(i)

        res = []
        for word in smalls:
            res.append(hit[word])
        return res

复杂度分析

时间复杂度：O(n m)，n = len(big)， m = len(smalls) 空间复杂度：O(m k)，k = max(len(smalls[i])) 即k是smalls中最长字符串的长度

[RestlessBreeze]

code

struct TrieNode
{
    int id;
    TrieNode* child[26];
    TrieNode()
    {
        id = -1;
        for (int i = 0; i < 26; i++)
            child[i] = nullptr;
    }
};

class Solution {
public:
    TrieNode* root = new TrieNode();
public:
    void Insert(string& s, int id)
    {
        TrieNode* temp = root;
        for (char c : s)
        {
            if (!temp->child[c - 'a'])
                temp->child[c - 'a'] = new TrieNode();
            temp = temp->child[c - 'a'];
        }
        temp->id = id;
    }

    void search(string& s, vector<vector<int>>& res, int i)
    {
        TrieNode* temp = root;
        for (char c : s)
        {
            if (!temp->child[c - 'a'])
                break;
            else
            {
                temp = temp->child[c - 'a'];
                if (temp->id != -1)
                {
                    res[temp->id].push_back(i);
                }
            }
        }
    }

    vector<vector<int>> multiSearch(string big, vector<string>& smalls) 
    {
        int n = smalls.size();
        int m = big.length();
        vector<vector<int>> res(n, vector<int>{});

        for (int i = 0; i < n; i++)
        {
            if (smalls[i].length() == 0)
                continue;
            Insert(smalls[i], i);
        }

        for (int i = 0; i < m; i++)
        {
            string temp = big.substr(i, m - i);
            search(temp, res, i);
        }

        return res;
    }
};

[NorthSeacoder]

var multiSearch = function (big, smalls) {
    const res = Array.from(smalls, () => []);
    const trie = {};
    smalls.forEach((str, index) => {
        let node = trie;
        for (let char of str) {
            if (!node[char]) node[char] = {};
            node = node[char];
        }
        node.isWord = true;
        node.index = index;
    });
    for (let i in big) {
        let node = trie;
        for (let inx = i; inx < big.length; inx++) {
            let char = big[inx];
            if (!node[char]) break;
            node = node[char];
            const {isWord, index} = node;
            if (!!isWord) {
                res[index].push(i);
            }
        }
    }
    return res;
};

[huizsh]

class Solution {

private Node root = new Node();

public int[][] multiSearch(String big, String[] smalls) {

    int n = smalls.length;
    // 初始化结果集
    List<Integer>[] res = new List[n];
    for(int i = 0 ; i < n ; i++)
        res[i] = new ArrayList<>();
    // 建树
    for(int i = 0 ; i < smalls.length; i++)
        insert(smalls[i], i);

    for(int i = 0 ; i < big.length(); i++){

        Node tmp = root;

        for(int j = i ; j < big.length(); j++){
            //不存在以该串为prefix的敏感词
            if(tmp.children[big.charAt(j) - 'a'] == null)
                break;

            tmp = tmp.children[big.charAt(j) - 'a'];

            if(tmp.isWord)
                res[tmp.id].add(i);
        }
    }
    // 返回二维数组
    int[][] ret = new int[n][];

    for(int i = 0 ; i < n ; i++){

        ret[i] = new int[res[i].size()];

        for(int j = 0 ; j < ret[i].length; j++)
            ret[i][j] = res[i].get(j);
    }

    return ret;
}

private void insert(String word, int id){

    Node tmp = root;

    for(int i = 0; i < word.length(); i++){

        if(tmp.children[word.charAt(i) - 'a'] == null)
            tmp.children[word.charAt(i) - 'a'] = new Node();

        tmp = tmp.children[word.charAt(i) - 'a'];
    }

    tmp.isWord = true;
    tmp.id = id;
}

class Node {

    Node[] children;
    boolean isWord;
    int id;

    public Node() {

        children = new Node[26];
        isWord = false;
        id = 0;
    }
}

}

[FireHaoSky]

思路：多次搜索，前缀树

代码：python

class Trie:
    def __init__(self, words):
        self.d = {}
        for word in words:
            t = self.d
            for w in word:
                if w not in t:
                    t[w] = {}
                t = t[w]
            t['end'] = word
    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)
        hit = collections.defaultdict(list)

        for i in range(len(big)):
            matchs = trie.search(big[i:])
            for word in matchs:
                hit[word].append(i)

        res = []
        for word in smalls:
            res.append(hit[word])
        return res

复杂度分析：

"""
时间复杂度：O(len(big)len(small))
空间复杂度：O(len(small)max(len(smalls[i])))
"""

[snmyj]

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        postion = []
        for i in range(len(smalls)):
            small = smalls[i]
            length = max(len(small), 1)
            k = 0
            p = []
            while k + length <= len(big):
                if big[k:k+length] == small:
                    p.append(k)
                k += 1
            postion.append(p)
        return postion

[Diana21170648]

思路

前缀树

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

**复杂度分析**
- 时间复杂度：T=O(n*k)，n为长句的长度，k为最长单词的长度
- 空间复杂度：S=O(s)，匹配成功的位置的次数

[chocolate-emperor]

class Solution {
public:
    struct Node{
        int cnt;
        int precnt;
        Node* ne[26]; //序号对应字符
        Node():cnt(0),precnt(0),ne(){}
    };
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        vector<vector<int>> res;
        unordered_map<string,int>word2index;

        if(smalls.size()<1)   return res;
        for(int i = 0; i< smalls.size();i++){
            vector<int>tmp;
            res.emplace_back(tmp);
       }
        if(big.size()<1)    return res;

        //非空情况下，采用trie树解决
        Node* root = new Node();
        int index = 0;
        for(string i:smalls){

            //trie上插入一个单词,按序遍历字母
            word2index[i] = index++;
            Node* curr = root;
            for(char j:i){
                int index = j-'a';
                if(curr->ne[index]==nullptr){
                    curr->ne[index] = new Node();
                }
                curr = curr->ne[index];
                curr->precnt +=1;
            }
            curr->cnt+=1;
        }

        //判断各字符为首的字符串前缀能否匹配到trie上的词
        int l = big.size();
        for(int i=0;i<l;i++){

            Node* curr = root;
            string word = "";
            for(int j = i; j<l;j++){
                int num = big[j] - 'a';
                if(curr->ne[num]==nullptr)  break;

                word += big[j];
                curr = curr->ne[num];
                if(curr->cnt>0) {
                    res[word2index[word]].emplace_back(i);
                }
            }    

        }

        return res;
    }
};

[bookyue]

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie();

        for (int i = 0; i < smalls.length; i++)
            trie.insert(smalls[i], i);

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < smalls.length; i++)
            ans.add(new ArrayList<>());

        for (int i = 0; i < big.length(); i++)
            for (var id : trie.hasPrefix(big.substring(i)))
                ans.get(id).add(i);

        return ans.stream()
                .map(arr -> arr.stream().mapToInt(i -> i).toArray())
                .toArray(int[][]::new);
    }

    private static class Trie {
        private final Trie[] children;
        private boolean isEnd;
        private int id;

        private Trie() {
            children = new Trie[26];
            isEnd = false;
            id = -1;
        }

        private void insert(String word, int id) {
            if (word.isBlank()) return;

            Trie node = this;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null)
                    node.children[idx] = new Trie();

                node = node.children[idx];
            }

            node.isEnd = true;
            node.id = id;
        }

        private List<Integer> hasPrefix(String search) {
            Trie node = this;
            List<Integer> ids = new ArrayList<>();
            for (char c : search.toCharArray()) {
                int idx = c - 'a';

                if (node.isEnd) ids.add(node.id);

                if (node.children[idx] == null) return ids;

                node = node.children[idx];
            }

            if (node.isEnd) ids.add(node.id);
            return ids;
        }
    }
}

[harperz24]

class TrieNode:
    def __init__(self, ch=""):
        self.ch = ch
        self.children = {}
        self.stored_word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, words):
        for word in words:
            cur = self.root
            for ch in word:
                if ch not in cur.children:
                    cur.children[ch] = TrieNode(ch)
                cur = cur.children[ch]
            cur.stored_word = word

    def search(self, s):
        res = []
        cur = self.root 

        for ch in s:
            if ch not in cur.children:
                break
            cur = cur.children[ch]
            if cur.stored_word:    
                res.append(cur.stored_word) 
        return res

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        trie = Trie()
        trie.insert(smalls)
        hit = collections.defaultdict(list)

        for i in range(len(big)):
            matches = trie.search(big[i:])
            for word in matches:
                hit[word].append(i)

        res = []
        for word in smalls:
            res.append(hit[word])
        return res

    # time：O(len(big) * len(smalls))
    # space：O(len(smalls) * max len of smalls[i])

[enrilwang]

var multiSearch = function (big, smalls) { const res = Array.from(smalls, () => []); const trie = {}; smalls.forEach((str, index) => { let node = trie; for (let char of str) { if (!node[char]) node[char] = {}; node = node[char]; } node.isWord = true; node.index = index; }); for (let i in big) { let node = trie; for (let inx = i; inx < big.length; inx++) { let char = big[inx]; if (!node[char]) break; node = node[char]; const {isWord, index} = node; if (!!isWord) { res[index].push(i); } } } return res; };

[Hughlin07]

class Solution {

class Trie{
    TrieNode root;
    public Trie(String[] words){
        root = new TrieNode();
        for(String word : words){
            TrieNode node = root;
            for(char w : word.toCharArray()){
                int i = w - 'a';
                if(node.next[i] == null){
                    node.next[i] = new TrieNode();
                }
                node = node.next[i];
            }
            node.end = word;
        }
    }

    public List<String> search(String str){
        TrieNode node = root;
        List<String> res = new ArrayList<>();
        for(char c : str.toCharArray()){
            int i = c - 'a';
            if(node.next[i] == null){
                break;
            }
            node = node.next[i];
            if(node.end != null){
                res.add(node.end);
            }
        }
        return res;
    }  
}

class TrieNode{
    String end;
    TrieNode[] next = new TrieNode[26];
}

public int[][] multiSearch(String big, String[] smalls) {
    Trie trie = new Trie(smalls);
    Map<String, List<Integer>> hit = new HashMap<>();
    for(int i = 0; i < big.length(); i++){
        List<String> matchs = trie.search(big.substring(i));
        for(String word: matchs){
            if(!hit.containsKey(word)){
                hit.put(word, new ArrayList<>());
            }
            hit.get(word).add(i);
        }
    }

    int[][] res = new int[smalls.length][];
    for(int i = 0; i < smalls.length; i++){
        List<Integer> list = hit.get(smalls[i]);
        if(list == null){
            res[i] = new int[0];
            continue;
        }
        int size = list.size();
        res[i] = new int[size];
        for(int j = 0; j < size; j++){
            res[i][j] = list.get(j);
        }
    }
    return res;
}

}

[Lydia61]

17. 多次搜索

思路

前缀哈希

代码

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        //给定一个字符串数组，查找这些字符串在原串上出现的位置
        unordered_map<string,vector<int>>map;
        int n=big.size();
        for(int i=0;i<n;i++){
            string t=big.substr(i);
            for(int j=1;j<=t.size();j++){
                //substr函数是左开右闭，所以一直循环到=t.size()

                //说明t.substr(0,j)出现在以big[i]开头的字符串的前缀上
                map[t.substr(0,j)].emplace_back(i);
            }
        }
        vector<vector<int>> res;

        for(string word:smalls){
            res.emplace_back(map[word]);
        }

        return res;
    }
};

[tzuikuo]

思路

代码

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        vector<vector<int>> ans;
        for(auto P : smalls){
            ans.push_back({});
            if(P.empty()){
                continue;
            }

            //计算失配函数
            vector<int> f(P.size()+1);
            getFail(P,f);

            //在big中查找字符串P的所有出现位置
            int j = 0;
            for(int i=0;i<big.size();++i){
                while(j && P[j] != big[i]){
                    j = f[j];
                }
                if(P[j] == big[i]){
                    j++;
                }
                if(j == P.size()){//找到了P
                    ans.back().push_back(i-(j-1));
                }
            }

        }
        return ans;
    }

    void getFail(const string& P,vector<int>& f){
        f[0] = 0;
        f[1] = 0;
        for(int j=1;j<P.size();++j){
            int k = f[j];
            while(k && P[k] != P[j]){
                k = f[k];
            }

            if(P[k] == P[j]){
                f[j+1] = k + 1;
            }else{
                f[j+1] = 0;
            }
        }
    }
};

复杂度分析 -待定

[joemonkeylee]

        private int[][] res;
        private string gbig;
        public int[][] MultiSearch(string big, string[] smalls)
        {
            res = new int[smalls.Length][];
            gbig = big;
            for (int i = 0; i < smalls.Length; i++)
            {
                MultiSeachBuild(i, smalls[i]);
            }
            return res;
        }

        public void MultiSeachBuild(int position, string s)
        {
            if (s == "" || gbig == "")
            {
                res[position] = new int[0];
                return;
            }
            int index = 0;
            List<int> ls = new List<int>();
            while ((index = gbig.IndexOf(s, index) + 1) != 0) 
            {
                ls.Add(index - 1);
            }
            res[position] = ls.ToArray();
        }

[JasonQiu]

class Trie:
    def __init__(self, words):
        self.d = {}
        for word in words:
            current = self.d
            for c in word:
                if c not in t:
                    current[c] = {}
                current = current[c]
            current['end'] = word

    def search(self, string):
        current = self.d
        res = []
        for w in string:
            if w not in current:
                break
            current = current[w]
            if 'end' in current:
                res.append(current['end'])
        return res

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        trie = Trie(smalls)
        hit = defaultdict(list)

        for i in range(len(big)):
            matchs = trie.search(big[i:])
            for word in matchs:
                hit[word].append(i)

        result = []
        for word in smalls:
            result.append(hit[word])
        return result

[kangliqi1]

public int[][] multiSearch(String big, String[] smalls) {

int[][] res = new int[smalls.length][];

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

    int startIdx = 0;
    while (true) {

        int idx = big.indexOf(small, startIdx);
        if (idx == -1)
            break;

        cur.add(idx);
        startIdx = idx + 1;
    }

    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;

}

[X1AOX1A]

class Solution { public int[][] multiSearch(String big, String[] smalls) { if(smalls==null || smalls.length==0) return new int[][]{}; int N = smalls.length; int[][] res = new int[N][];

    for(int i = 0 ; i < N ; ++i){
        int index = 0, j=0;
        <!-- 特殊情况：字串是"",此时用indexOf的化会直接匹配到首个元素的位置，
             所以拿出来特殊处理一下 -->
        if("".equals(smalls[i])){
            res[i] = new int[]{};
            continue;
        }
        <!-- list存放当前子串出现的所有位置 -->
        ArrayList<Integer> list = new ArrayList<>();
        while(big.indexOf(smalls[i],index)!=-1){
            list.add(big.indexOf(smalls[i],index));
            <!-- 从当前匹配到的位置的下一个位置开始匹配 -->
            index = big.indexOf(smalls[i],index) + 1;
        }
        <!-- 根据子串出现次数，为当前数组初始化 -->
        res[i] = new int[list.size()];
        <!-- 赋值 -->
        for(int k : list){
            res[i][j++] = k;
        }
    }
    return res;
}

}

作者：管永升 链接：https://leetcode.cn/problems/multi-search-lcci/solutions/2218726/cai-niao-jie-fa-shi-jian-615-ms-ji-bai-1-i7tn/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[Jetery]

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

[kofzhang]

没有思路

KMP不会，记不住

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        res = []
        for i in smalls:
            if i=="":
                res.append([])
                continue
            t = i+"#"+big
            pi = [0]*len(t)
            for j in range(1,len(t)):
                k = pi[j-1]
                while k>0 and t[j]!=t[k]:
                    k = pi[k-1]
                if t[j]==t[k]:
                    k+=1
                pi[j]=k
            res.append([p-2*len(i) for p in range(len(t)) if pi[p]==len(i)])
        return res 

[chanceyliu]

代码

function treeNode(val?: any) {
  this.val = val
  this.children = {}
}

function multiSearch(big: string, smalls: string[]): number[][] {
  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
};