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

[yanglr]

思路

可以用 Trie树来做。

具体步骤有参考suukii的仓库, 代码完全是自己写的~

方法: Trie树

把短字符串存到 Trie 中，保证 Trie 的高度尽量的小。

• 以 dictionary 数组构建 Trie，并在结束节点记录每个短串在 dictionary 数组中的下标；

• 遍历 sentence 字符串，截取所有以 longest 为长度的子串(longest 是 dictionary 中最长的单词长度)，拿到 Trie 中去寻找所有匹配的短串，返回所有匹配到的下标，根据下标把当前子串的位置更新到对应的结果数组中。

Trie 的操作：

• insert: 把单词的 下标 存到最后的节点中
• search: 需要返回寻找路径中匹配到的所有单词的下标

代码

实现语言: C++

class Solution {
private:
    struct Node {
        int idx;
        vector<Node*> children;
        Node() : idx(-1), children(26, nullptr) {}
    };
    struct Trie {
        Node* root;
        Trie() : root(new Node()) {}
        void insert(string& word, int idx)
        {
            Node* p = root;
            for (char& c : word) {
                c -= 'a';
                if (p->children[c] == nullptr)
                {
                    p->children[c] = new Node();
                }
                p = p->children[c];
            }
            p->idx = idx;
        }
    };    
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        unordered_map<string, vector<int>> cache;
        const int n = big.length();
        const int m = smalls.size();
        vector<vector<int>> res(m);

        Trie trie = Trie();
        // 构造前缀树
        for (int i = 0; i < m; i++)
        {
            trie.insert(smalls[i], i);
        }
        for (int i = 0; i < n; i++)
        {
            int j = i;
            Node* node = trie.root;
            while (j < n && node->children[big[j] - 'a'])
            {
                node = node->children[big[j] - 'a'];
                if (node->idx != -1)
                {
                    res[node->idx].push_back(i);
                }
                j++;
            }
        }
        return res;
    }
};

复杂度分析

	时间	空间
insert	O(len(dictionary)*avg), avg 是短串的平均长度	O(n^{avg}), n 是字符集大小，avg 是短串的平均长度
search	O(maxLen(dictionary)*len(dictionary))	O(n^{m})

[chakochako]

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

[for123s]

代码

• 语言支持：C++

C++ Code:

struct triNode{
    vector<triNode*> children;
    bool end;
    int idx;
    triNode()
    {
        end = false;
        idx = 0;
        children.assign(26,NULL);
    }
};

class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        triNode* root = new triNode();
        for(int i=0;i<smalls.size();i++)
        {
            triNode* temp = root;
            for(int j=0;j<smalls[i].size();j++)
            {
                int idx = smalls[i][j] - 'a';
                if(!temp->children[idx])
                    temp->children[idx] = new triNode();
                temp = temp->children[idx];
            }
            temp->end = true;
            temp->idx = i;
        }
        vector<vector<int>> res(smalls.size(),vector<int>(0,{}));
        for(int i=0;i<big.size();i++)
        {
            triNode* temp = root;
            int j = i;
            while(temp&&j<big.size())
            {
                int idx = big[j] - 'a';
                if(temp->children[idx])
                {
                    temp = temp->children[idx];
                    if(temp->end)
                    {
                        res[temp->idx].push_back(i);
                    }
                    j++;
                }
                else
                    break;
            }
        }
        return res;
    }
};

[biancaone]

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

[pophy]

思路

把所有短字符 smalls 放入Trie

• Trie.search 实现方法：传入str 找到所有满足以str为头的字符串

• 从前往后遍历big，将找到的match放入matchlist

• 整理matchlist并归并到indexmap

• 根据smalls的顺序输出结果

Java Code

public class MultiSearch {
    public int[][] multiSearch(String big, String[] smalls) {
        Trie trie = new Trie();
        for (String word : smalls) {
            trie.insert(word);
        }
        Map<String, List<Integer>> indexMap = new HashMap<>();
        for (int i = 0; i < big.length(); i++) {
            String word = big.substring(i);
            List<String> matches = trie.search(word);
            for (String match : matches) {
                indexMap.computeIfAbsent(match, x -> new ArrayList()).add(i);
            }
        }
        int[][] res = new int[smalls.length][];
        for (int i = 0; i < smalls.length; i++) {
            List<Integer> indexList = indexMap.get(smalls[i]);
            int[] indexArr = new int[indexList == null ? 0 : indexList.size()];
            for (int j = 0; j < indexArr.length; j++) {
                indexArr[j] = indexList.get(j);
            }
            res[i] = indexArr;
        }
        return res;
    }
    private static class Trie {
        TrieNode root = new TrieNode();
        public List<String> search(String str) {
            List<String> result = new ArrayList<>();
            TrieNode p = root;
            for (char c : str.toCharArray()) {
                if (p.children.get(c) == null) {
                    break;
                }
                p = p.children.get(c);
                if (p.word != null) {
                    result.add(p.word);
                }
            }
            return result;
        }
        public void insert(String str) {
            TrieNode p = root;
            for (char c : str.toCharArray()) {
                if (p.children.get(c) == null) {
                    p.children.put(c, new TrieNode());
                }
                p = p.children.get(c);
            }
            p.word = str;
        }
        private static class TrieNode {
            String word = null;
            Map<Character, TrieNode> children = new HashMap<>();
        }
    }
}

[qixuan-code]

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

[JiangyanLiNEU]

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 search(big, small):
        trie = Trie(small)
       check = {}

        for i in range(len(big)):
            match = trie.search(big[i:])
            for word in match:
                check[word].append(i)
        
        res = []
        for word in small:
            res.append(check[word])
        return res

[leo173701]

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 search(big, small):
        trie = Trie(small)
       check = {}

        for i in range(len(big)):
            match = trie.search(big[i:])
            for word in match:
                check[word].append(i)
        
        res = []
        for word in small:
            res.append(check[word])
        return res

[yachtcoder]

Rolling hash and Trie.

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.eow = False
        self.word = None

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

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            node = node.children[c]
        node.eow = True
        node.word = word

    def findWords(self, prefix):
        ret = []
        node = self.root
        for c in prefix:
            if c not in node.children:
                break
            node = node.children[c]
            if node.eow:
                ret.append(node.word)
        return ret

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        trie = Trie()
        smallidx = {}

        for i, s in enumerate(smalls):
            trie.insert(s)
            smallidx[s] = i

        ret = [[] for _ in range(len(smalls))]

        for i in range(len(big)):
            words = trie.findWords(big[i:])
            for s in words:
                if s not in smallidx: continue
                ret[smallidx[s]].append(i)
        return ret

    def multiSearchRollingHash(self, big: str, smalls: List[str]) -> List[List[int]]:
        if not big: return [[] for _ in range(len(smalls))]
        def c2n(c):
            return ord(c) - ord('a')
        def get_hash(s, size):
            base = 331
            mod = 99999199999
            hash = 0
            hashset = defaultdict(list)
            for i in range(size):
                n = c2n(s[i])
                hash = hash*base + n
            hash = hash%mod
            mag = pow(base, size-1, mod)
            hashset[hash].append(0)
            for i in range(size, len(s)):
                left = i - size
                hash = ((hash - mag*c2n(s[left]))*base + c2n(s[i]))%mod
                hashset[hash].append(i-size+1)
            return hashset
        
        ls = set([len(s) for s in smalls])
        hash_by_length = defaultdict(list)
        for l in ls:
            if l <= len(big):
                hash_by_length[l]=get_hash(big, l)
        
        ret = []
        for s in smalls:
            if len(s) == 0 or len(s) > len(big): 
                ret.append([])
                continue
            hash = list(get_hash(s, len(s)).keys())[0]
            bighash = hash_by_length[len(s)]
            locs = bighash[hash]
            ret.append(locs)
        return ret

[zhangzz2015]

思路

• 建立small的trie树，记录下small 字符串最后结束后对应的index放入count，在big 进行递归search，当我们找到一个count>=0，表明我们匹配到一个子串的结束的字符，通过small字符串的大小，我们可反推出在big的字符串的起始位置，放入对应的结果的vector里。时间的复杂度，建立trie的时间复杂度加上遍历big字符的 O( n *m + k^2) n 为small的字符串个数，m为平均字符串的大小，k 为 big 的字符串的大小。

关键点

代码

• 语言支持：C++

C++ Code:

struct triNode
{
    vector<triNode*> child; 
    int count;

    triNode()
    {
        child.assign(26, NULL); 
        count=-1; 
    }

}; 
class Solution {
public:
    triNode* pRoot; 
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {

        pRoot = new triNode();         
        for(int i=0; i< smalls.size(); i++)
        {
            triNode* pCurrent = pRoot; 
            for(int j=0; j< smalls[i].size(); j++)
            {
                int index = smalls[i][j] - 'a'; 
                if(pCurrent->child[index]==NULL)
                {
                    pCurrent->child[index] = new triNode(); 
                }
                pCurrent = pCurrent->child[index]; 
            }
            pCurrent->count = i; 
        }
        vector<vector<int>>  ret(smalls.size()); 
        for(int i=0; i< big.size(); i++)
        {
             dfs(big, i, ret, pRoot, smalls);
        }        
        return ret; 
    }
    void dfs(string& big, int start, vector<vector<int>>& ret, triNode* root, vector<string>& smalls)
    {
        if(start>=big.size())
          return ;
           int index = big[start]- 'a'; 
           if(root->child[index])
           {
               if(root->child[index]->count>=0)
               {
                   //cout<< "index:" << index << "start:" << start << "count" << root->child[index]->count << "\n"; 
                   ret[root->child[index]->count].push_back(start - smalls[root->child[index]->count].size()+1);
               }
               dfs(big, start+1, ret, root->child[index], smalls); 
           }
    }
};

[Daniel-Zheng]

思路

前缀树。

代码(C++)

struct TrieNode{
    int sid;
    TrieNode *child[26];
    TrieNode(){
        sid=-1;
        for(int i=0;i<26;++i) child[i]=NULL;
    }
};
class Solution {
private:
    TrieNode *root=new TrieNode();
public:
    void insert(string word,int s){
        int n=word.size();
        TrieNode *cur=root;
        for(int i=0;i<n;++i){
            int cid=word.at(i)-'a';
            if(cur->child[cid]==NULL) cur->child[cid]=new TrieNode();
            cur=cur->child[cid];
        }
        cur->sid=s;
    }
    void search(string word,vector<vector<int>>& ans,int bid){
        int n=word.size();
        TrieNode *cur=root;
        for(int i=0;i<n;++i){
            int cid=word.at(i)-'a';
            if(cur->sid!=-1) ans[cur->sid].push_back(bid);
            if(cur->child[cid]==NULL) return ;
            cur=cur->child[cid];
        }
        if(cur->sid!=-1) ans[cur->sid].push_back(bid);
    }
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        int n=smalls.size(),m=big.size();
        vector<vector<int>> ans(n,vector<int>{});
        for(int i=0;i<n;++i){
            if(smalls[i].size()==0) continue;
            insert(smalls[i],i);
        }
        for(int i=0;i<m;++i){
            string word=big.substr(i,m-i);
            search(word,ans,i);
        }
        return ans;
    }
};

复杂度分析

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

[hwpanda]

class Solution {
  public static int[][] multiSearch(String big, String[] smalls) {
      int[][]multiSearch = new int[smalls.length][];
      for(int i = 0;i < smalls.length; i++){
          String small = smalls[i];
          if("".equals(small)){
              multiSearch[0] = new int[0];
              return multiSearch;
          }
          int g =0;
          int[] nu = new int[10000];

          for(int j =0;j <= big.length()-small.length(); j++){
              String mid = big.substring(j,j+small.length());
              if(mid.contains(small)){
                  int index = j;
                  //multiSearch[i][g] = index;
                  nu[g] = index;
                  g++;

              }
          }
          multiSearch[i] = new int[g];
          for (int k = 0; k <multiSearch[i].length ; k++) {
              multiSearch[i][k] = nu[k];
          }

      }
      return multiSearch;
  }
}

[laofuWF]

class Trie:
    def __init__(self, words):
        self.root = {}
        for word in words:
            current = self.root
            for char in word:
                if char not in current:
                    current[char] = {}
                current = current[char]
            # mark the end
            current['end'] = word
    
    def search(self, word):
        current = self.root
        res = []
        for char in word:
            if char not in current:
                break
            current = current[char]
            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)
        matches = collections.defaultdict(list)

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

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