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

[tiandao043]

思路

改了前面的代码，今天回来有时间补一下kmp。

代码

class Solution {
class Node{
public:
    Node* child[26];
    bool isEnd;
    int value;

    Node() {
        isEnd=false;
        memset(child,0,sizeof(child));
        value=0;
    }
};

public:
    Node* root=new Node();
    void insert(string key, int val) {
        Node* m=root;
        for(char ch : key){
            if(m->child[ch-'a']==NULL){
                m->child[ch-'a']=new Node();
            }
            m=m->child[ch-'a'];
        }
        m->isEnd=true;
        m->value=val;
    }
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        int n = smalls.size();
        vector<vector<int>> res;
        vector<int> ind;
        for(int i=0;i<n;i++){
            res.push_back(ind);
        }
        for(int i=0;i<n;i++){
            insert(smalls[i],i);
        }
        for(int i=0;i<big.length();i++){
            Node* tmp= root;
            for(int j=i;j<big.length();j++){
                if(tmp->child[big[j]-'a']==NULL){
                    break;
                }
                tmp=tmp->child[big[j]-'a'];
                if(tmp->isEnd)res[tmp->value].push_back(i);
            }
        }
        return res;
    }
};

O(N∗K)，其中 K 是敏感词中最长单词长度，N 是长句的长度。 O(S)O(S), S 为所有匹配成功的位置的个数。

[snmyj]

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {

          int n=smalls.size();
          vector<vector<int>> ans(n,vector<int>());
          for(int k=0;k<n;k++){
              for(int j=0;j<big.size();j++){
                  for(int i=0;i<smalls[k].size();i++){
                      if(smalls[k][i]!=big[j]) {
                          j=j-i;
                          break;
                      }
                      else j++;
                      if(i==smalls[k].size()-1) {
                          ans[k].push_back(j-smalls[k].length());
                           j=j-i-1;
                          break;

                      }
                  }
              }
          }
          return ans;
    }
};

[bwspsu]

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

[Abby-xu]

抄答案

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

[JancerWu]

先写一个暴力法

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = big.length();
        for (String small : smalls) {
            int len = small.length();
            if (len == 0) continue;
            List<Integer> tmp = new ArrayList<>();
            for (int l = 0, r = len - 1; r < n; l++, r++) {
                if (check(big, small, l, r)) tmp.add(l);
            }
            ans.add(tmp);
        }
        int[][] res = new int[smalls.length][0];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = new int[ans.get(i).size()];
            for (int j = 0; j < ans.get(i).size(); j++) {
                res[i][j] = ans.get(i).get(j);
            }
        }
        return res;
    }

    public boolean check(String big, String small, int start, int end) {
        int cnt = 0;
        for (int i = start; i <= end; i++) {
            if (big.charAt(i) != small.charAt(cnt++)) return false;
        }
        return true;
    }
}

[bookyue]

code

    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.prefixIDs(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> prefixIDs(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;
        }
    }

[Elsa-zhang]

class Solution:

    def multiSearch(self, big: str, smalls: list[str]):
        postion = []
        for small in smalls:
            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

big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]   
s = Solution()
ans = s.multiSearch(big, smalls)
print(ans)

[liuajingliu]

代码实现

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

复杂度分析

• 时间复杂度：$(N^2)$
• 空间复杂度: $O(S)$

[JancerWu]

class Solution {
    class Node{
        int index = -1;
        Node[] next;
        Node(){
            next = new Node[26]; 
        }
    }
    Node root = new Node();
    List<List<Integer>> tmp = new ArrayList<>();
    public int[][] multiSearch(String big, String[] smalls) {
        for (int i = 0; i < smalls.length; i++) tmp.add(new ArrayList<>());
        buildInfixTree(smalls);
        int n = big.length();
        for (int i = n - 1; i >= 0; i--) {
            search(i, big);
        }
        int[][] ans = new int[smalls.length][0];
        for (int i = 0; i < tmp.size(); i++) {
            ans[i] = new int[tmp.get(i).size()];
            int cnt = 0;
            for (int j = tmp.get(i).size() - 1; j >= 0; j--) {
                ans[i][cnt++] = tmp.get(i).get(j);
            }
        }
        return ans;
    }

    public void search(int end, String big) {
        Node cur = root;
        for (int i = end; i >= 0; i--) {
            int pos = big.charAt(i) - 'a';
            if (cur.next[pos] == null) return;
            if (cur.next[pos].index != -1) tmp.get(cur.next[pos].index).add(i);
            cur = cur.next[pos];
        }
    }

    public void buildInfixTree(String[] smalls) {
        int n = smalls.length;
        for (int i = 0; i < n; i++) {
            String s = smalls[i];
            Node cur = root;
            for (int j = s.length() - 1; j >= 0; j--) {
                int pos = s.charAt(j)-'a';
                if (cur.next[pos] == null) cur.next[pos] = new Node();
                cur = cur.next[pos];
            }
            cur.index = i;
        }
    }
}

[klspta]

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>> map = new HashMap<>();
        for(int i = 0; i < big.length(); i++){
            List<String> matchs = trie.search(big.substring(i));
            for(String word : matchs){
                List<Integer> list = map.getOrDefault(word, new ArrayList<>());
                list.add(i);
                map.put(word, list);
            }
        }

        int[][] res = new int[smalls.length][];
        for(int i = 0; i < smalls.length; i++){
            List<Integer> list = map.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;
    }
}

[mayloveless]

思路

trie树

代码

/**
 * @param {string} big
 * @param {string[]} smalls
 * @return {number[][]}
 */

function TrieNode (data) {
    this.data = data
    this.smallIdx = -1;
    this.children = {}
}

var multiSearch = function(big, smalls) {
    const res = smalls.map(() => [])
    if (!big) {
        return res
    }
    const Tree = new TrieNode('/');
    let cur;
    smalls.forEach((small, index) => {
        cur = Tree;
        for (let i = 0; i < small.length; i++) {
            if (!cur.children[small[i]]) {
                cur.children[small[i]] = new TrieNode(small[i])
            }
            cur = cur.children[small[i]]
        }
        cur.smallIdx = index
    });

    for (let i = 0; i < big.length; i++) {
        let cur = Tree;
        for (let j = i; j < big.length; j++) {
            if (!cur.children[big[j]]) {
                break
            }
            cur = cur.children[big[j]]
            if (cur.smallIdx !== -1) {
                res[cur.smallIdx].push(i)
            }
        }
    }
    return res
};

复杂度

时间 O(N^2) 空间 O(S)

[buer1121]

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

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

[paopaohua]

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++){
                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;
        }
    }
}

[whoam-challenge]

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

[RestlessBreeze]

code

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