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

[yetfan]

思路 Trie 构建smalls，用end来表示该单词对应在smalls中的位置 然后遍历big每个字符开始寻找是否在Trie中，search一次则进行记录，最后返回并整理

代码

class Trie:
    def __init__(self):
        self.children = {}
        self.end = -1

    def insert(self, word, index):
        node = self
        for c in word:
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]
        node.end = index

    def search(self, word):
        res = []
        node = self
        for c in word:
            if c not in node.children:
                break
            node = node.children[c]
            if node.end != -1:
                res.append(node.end)
        return res

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        res = []
        t = Trie()
        for index, word in enumerate(smalls):
            t.insert(word, index)
            res.append([])

        for i in range(len(big)):
            match_words = t.search(big[i:])
            for index in match_words:
                res[index].append(i)
        print(res)
        return res

复杂度 时间 O( max(map(len，smalls)) * len(big) ) 空间 O(Trie树的节点数+存储的结果数)

[ZacheryCao]

Idea

Trie + DFS

Code

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        if not big:
            return [[] for i in smalls]
        if not smalls:
            return []
        root = {}
        m = collections.defaultdict(list)
        for word in smalls:
            cur = root
            for c in word:
                cur = cur.setdefault(c,{})
            cur["#"] = word

        for i in range(len(big)):
            cur = root
            if big[i] in cur:
                index = i
                while True:
                    if index >= len(big) or big[index] not in cur:
                        break
                    cur = cur[big[index]]
                    if "#" in cur:
                        m[cur["#"]].append(i)
                    index += 1
        ans = []
        for i in smalls:
            ans.append(m[i])
        return ans

Complexity:

Time: O(M*N). M: len(big). N: the total characters of smalls in worst case. Averagely should be the nodes for Trie built based on the smalls Sapce: O(N)

[Tao-Mao]

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

[xinhaoyi]

class TrieNode{ TrieNode[] childs; boolean isWord; public TrieNode(){ childs = new TrieNode[26]; } } class Solution { public int[][] multiSearch(String big, String[] smalls) { TrieNode root = new TrieNode(); Map<String,List> map = new HashMap<>(); //构建字典树 for (String small : smalls) { map.put(small,new ArrayList<>()); insert(root,small); } //寻找所有单词在big中的起始位置，并存放在map中 for(int i=0;i<big.length();i++){ search(root, i, big,map); } //输出结果 int[][] ans = new int[smalls.length][]; for (int i = 0; i < smalls.length; i++) { ans[i] = map.get(smalls[i]).stream().mapToInt(Integer::valueOf).toArray(); } return ans; }

//构建后缀树
public void insert(TrieNode root,String word){
    TrieNode node = root;
    for (int i = word.length()-1; i >=0; i--) {
        int idx = word.charAt(i)-'a';
        if(node.childs[idx]==null){
            node.childs[idx] = new TrieNode();
        }
        node = node.childs[idx];
    }
    node.isWord = true; //表示单词的结尾
}

//寻找以endPos结尾的所有单词的起始位置
public void search(TrieNode root,int endPos,String sentence,Map<String,List<Integer>> map){
    TrieNode node = root;
    StringBuilder builder = new StringBuilder(); //单词作为key
    for(int i=endPos;i>=0;i--){
        int idx = sentence.charAt(i)-'a';
        if(node.childs[idx]==null){
            break;
        }
        //由于字典树存的是后缀，故要倒着插入
        builder.insert(0,sentence.charAt(i));
        node = node.childs[idx];//递归寻找
        //找到某个单词，就把起始位置添加到map中
        if(node.isWord){
            map.get(builder.toString()).add(i);
        }
    }
}

}

[Tesla-1i]

class Trie:
    def __init__(self):
        self.children = {}
        self.end = -1

    def insert(self, word, index):
        node = self
        for c in word:
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]
        node.end = index

    def search(self, word):
        res = []
        node = self
        for c in word:
            if c not in node.children:
                break
            node = node.children[c]
            if node.end != -1:
                res.append(node.end)
        return res

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        res = []
        t = Trie()
        for index, word in enumerate(smalls):
            t.insert(word, index)
            res.append([])

        for i in range(len(big)):
            match_words = t.search(big[i:])
            for index in match_words:
                res[index].append(i)
        print(res)
        return res

[FlorenceLLL]

这个题真的是整不会了，看到答案里有一个解法，从TrieNode的构造、Trie的构造，search方法及其返回的List都让我叹为观止。

class Solution {
    class TrieNode {
        String end;
        //每一个node后都可能有26个字母
        TrieNode[] next = new TrieNode[26];
    }

    class Trie {
        TrieNode root;
        //根据smalls来构建树，树的结构是非叶子节点的end都为空，next指向一个TrieNode array； 叶子节点的end不为空
        public Trie(String[] words) {
            root = new TrieNode();
            for(String word : words) {
                TrieNode node = root;
                for(char ch : word.toCharArray()) {
                    int i = ch - 'a';

                    if(node.next[i] == null){
                        node.next[i] = new TrieNode();
                    }

                    node = node.next[i];
                }
                node.end = word;
            }
        }

       //search的方法和返回值也是神奇了，给一个str，返回的是smalls里面符合的所有元素
      //比如输入issi.. 输出["is","i"]
        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];
                //遍历完smalls的一个element
                if(node.end != null){
                    res.add(node.end);
                }
            }
            return res;
        }  
    }

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

[yan0327]

type TrieNode struct{
    children [26]*TrieNode
    isEnd bool
    id int
}
func (this *TrieNode) insert(word string, id int){
    node := this
    for _ , ch := range word{
        ch -= 'a'
        if node.children[ch] == nil{
            node.children[ch] = &TrieNode{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
    node.id = id
}
func (this *TrieNode) search (word string) bool{
    node := this
    for _,ch := range word{
        ch -= 'a'
        if node.children[ch] == nil{
            return false
        }
        node = node.children[ch]
    }
    return true
}

func multiSearch(big string, smalls []string) [][]int {
    n := len(smalls)
    trie := &TrieNode{}
    out := make([][]int,n)
    for i:=0;i<n;i++{
        out[i] = make([]int,0)
    }
    for i,x := range smalls{
        trie.insert(x,i)
    }
    for i:=0;i<len(big);i++{
        node := trie
        for j:=i;j<len(big);j++{
            if node.children[big[j]-'a'] == nil{
                break
            }
            node = node.children[big[j]-'a']
            if node.isEnd{
                out[node.id] = append(out[node.id],i)
            }
        }
    }
    return out
}

[Moin-Jer]

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

}

[xuhzyy]

class Node:
    def __init__(self):
        self.cnt = 0
        self.word = ''
        self.children = {}

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = Node()
            node = node.children[ch]
        node.cnt += 1
        node.word = word

    def search(self, s):
        res = []
        node = self.root
        for ch in s:
            if ch not in node.children:
                break
            node = node.children[ch]
            if node.cnt > 0:
                res.append(node.word)
        return res

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        trie = Trie()
        for small in smalls:
            trie.insert(small)
        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

[hdyhdy]

func multiSearch(big string, smalls []string) [][]int {
    res := make([][]int, len(smalls))
    for k, v := range smalls {
        c := []int{}
        if v == "" {
            res[k] = c
            continue
        }
        for i, _ := range big {
            if i + len(v) <= len(big) && big[i:i+len(v)] == v {
                c = append(c, i)
            }
        }
        res[k] = c
    }
    return res
}

[1149004121]

面试题 17.17. 多次搜索

思路

前缀树。将smalls构成前缀树，遍历big，判断从i开始，以j结尾的字符串能否构成前缀树单词的一部分。

代码

var multiSearch = function(big, smalls) {
    let root = new TrieNode();
    const len = big.length;
    const n = smalls.length;
    let res = new Array(n).fill(0).map(() => new Array());
    for(let i = 0; i < n; i++){
        insert(root, smalls[i], i);
    };
    for(let i = 0; i < len; i++){
        let node = root;
        for(let j = i; j < len; j++){
            let index = big.charCodeAt(j) - "a".charCodeAt();
            if(!node.children[index]) break;
            node = node.children[index];
            if(node.isEnd) res[node.id].push(i);
        }
    };
    return res;
};

function insert(root, word, id){
    let node = root;
    for(let char of word){
        let index = char.charCodeAt() - "a".charCodeAt();
        if(!node.children[index]) node.children[index] = new TrieNode();
        node = node.children[index];
    };
    node.id = id;
    node.isEnd = true;
}

function TrieNode(){
    this.children = new Array(26).fill(0);
    this.id = -1;
    this.isEnd = false;
}

复杂度分析

• 时间复杂度：O( LEN * L ) ，LEN为big长度。
• 空间复杂度：O(N*L) ，N为smalls长度，L为small平均长度。

[zhangzz2015]

思路

• 建立small string trie 树，注意节点需要记录是该字符串在vector中的位置，loop big，看是否能trie树中找到匹配的字符串，找的则返回相应的index。空间复杂度为O(n *m) n 为small string vector大小，m为平均string的大小，空间复杂度为O(k^2)，k为big string的大小。

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

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

}; class Solution { public: triNode* pRoot; vector<vector> multiSearch(string big, vector& 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++)
    {
         search(big, i, ret, smalls);
    }        
    return ret; 
}
void search(string& big, int start, vector<vector<int>>& ret, vector<string>& small)
{
      triNode* current = pRoot; 
      for(int i=start; i< big.size(); i++)
      {
            int index = big[i] - 'a'; 
            if(current->child[index]==NULL)
                return; 
            current = current->child[index]; 
            if(current->count>=0)
                ret[current->count].push_back(i-small[current->count].size()+1); 
      }
}

};

``

[Yrtryannn]

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

[KennethAlgol]

class Solution {
    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<>();
        }
    }
}

[LannyX]

思路

Trie

代码

class Solution {
    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;
    }

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

[callmeerika]

思路

前缀树

代码

var Trie = function () {
  this.children = {};
};

Trie.prototype.insert = function (word, index) {
  let node = this.children;
  for (let l of word) {
    if (!node[l]) node[l] = {};
    node = node[l];
  }
  node.index = index;
};

var multiSearch = function (big, smalls) {
  const position = smalls.map(vv => []);
  const trie = new Trie();
  smalls.forEach((vv, index) => {
    trie.insert(vv, index);
  });
  for (let i = 0; i < big.length; i++) {
    let node = trie.children;
    for (let j = i; j < big.length; j++) {
      let l = big[j];
      if (!node[l]) break;
      node = node[l];
      if (node.index !== undefined) {
        position[node.index].push(i);
      }
    }
  }
  return position;
};

复杂度

时间复杂度：O(mn)
空间复杂度：O(mk)

[ZJP1483469269]

思路

字符串哈希

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        n = len(big) + 1
        strhash = [0] * n
        p = [1] * n
        P = 131
        ans = [[] for _ in range(len(smalls))]
        for i in range(1 , n):
            nc = ord(big[i - 1]) - ord('a')
            strhash[i] = strhash[i-1] * P + nc
            p[i] = P * p[i-1]

        def get_hash(l , r):
            return strhash[r] - strhash[l - 1] * p[r - l + 1]

        j = 0
        for s in smalls:
            h = 0
            sn = len(s)
            if not sn:
                continue
            for c in s:
                h = h * P + (ord(c) - ord('a'))
            for i in range(1 , n - sn + 1):
                if get_hash(i , i + sn - 1) == h:
                    ans[j].append(i-1)
            j += 1

        return ans

[herbertpan]

思考

1. 第一反应是string.indexOf / strstr，感觉这也太没意思了。
2. 看了众人的提示才发现可以是trie，正好很久没写trie了来试试。

3. 区别就是别人写的trie是搜big的每一个index

   code

   class Solution {
   public int[][] multiSearch(String big, String[] smalls) {
       // Build a trie from small arr
       TrieNode root = new TrieNode(-1);
       for (int strIndex = 0; strIndex < smalls.length; strIndex++) {
           String str = smalls[strIndex];
           TrieNode node = root;
           for (int i = 0; i < str.length(); i++) {
               char ch = str.charAt(i);
               if (node.nodeArr[ch - 'a'] == null) {
                   node.nodeArr[ch - 'a'] = new TrieNode(-1);
   
               } 
               node = node.nodeArr[ch - 'a'];
           }
           // when finish a string, then write then its ansIndex
           node.ansIndex = strIndex;
       }
   
       // build a matrix for answer
       List<Integer>[] ans = new List[smalls.length];
       for (int i = 0; i < smalls.length; i++) {
           ans[i] = new ArrayList<>();
       }
   
       // check each individual 
       Queue<TrieNode> nodesToTrack = new LinkedList<>();
       nodesToTrack.offer(root);
       for (int i = 0; i < big.length(); i++) {
           int nodesNum = nodesToTrack.size();
           char ch = big.charAt(i);
           for (int j = 0; j < nodesNum; j++) {
               TrieNode node = nodesToTrack.poll();
               if (node.nodeArr[ch - 'a'] != null) {
                   node = node.nodeArr[ch - 'a'];
                   if (node.ansIndex != -1) {
                       ans[node.ansIndex].add(i - smalls[node.ansIndex].length() + 1);
                   }
                   nodesToTrack.offer(node);
               }
           }
   
           // insert back root, because we can always start from root
           nodesToTrack.offer(root);
       }
   
       int[][] result = new int[smalls.length][];
       for (int i = 0; i < smalls.length; i++) {
           result[i] = new int[ans[i].size()];
           for (int j = 0; j < ans[i].size(); j++) {
               result[i][j] = ans[i].get(j);
           }
       }
   
       return result;
   }
   
   private class TrieNode {
       TrieNode[] nodeArr;
       int ansIndex;
   
       public TrieNode(int ansIndex) {
           nodeArr = new TrieNode[26];
           this.ansIndex = ansIndex;
       }
   }
   }

complexity

1. time： O(k m + n Q) ==> k 为 smalls.length，m为smalls[I]的平均长度, n 为big 长度，Q为平均queue长度（最差结果为small.length） time: O(k * (m + n))
2. space: O(m^2)

[alongchong]

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

[CoreJa]

思路

• 前缀树：用所有small串构建前缀树，(设k为所有small串的字符数和则复杂度为$O(k)$)，然后用big的所有后缀子串去匹配(也可以理解为是从big的每个位置作为起点的串)，如果在前缀树里找到了那就保存结果，没找到就从下一个起点开始，匹配的复杂度为$O(nmax(smalls[i]))$，整体复杂度$O(k+nmax(smalls[i]))$。
• 哈希：这题的哈希解法比较另类，把big每个字符的下标用哈希存起来(存为列表即可)，然后遍历small子串，此时已经可以在$O(1)$时间获取big中每个字符的下标，直接用small去对比即可。遍历big串复杂度$O(n)$，对比子串复杂度$O(n*k)$(最坏情况smalls中每个字符都要和big的每个字符比)。最坏情况复杂度$O(nk)$
• KMP：求子串的问题当然也可以用KMP解决，和LC: 28完全类似，不过这里的KMP匹配到子串后不能停下来，而是要回退一步j，继续循环。设$m$为smalls的个数，则复杂度$O(k+m*n)$

代码

class Solution:
    # 哈希：这题的哈希解法比较另类，把`big`每个字符的下标用哈希存起来(存为列表即可)，然后遍历`small`子串，
    # 此时已经可以在$O(1)$时间获取`big`中每个字符的下标，直接用`small`去对比即可。遍历`big`串复杂度$O(n)$，
    # 对比子串复杂度$O(n*k)$(最坏情况`smalls`中每个字符都要和`big`的每个字符比)。最坏情况复杂度$O(nk)$
    def multiSearch1(self, big: str, smalls: List[str]) -> List[List[int]]:
        d = {}
        for i, ch in enumerate(big):
            if ch not in d:
                d[ch] = []
            d[ch] += [i]
        ans = []
        for i, small in enumerate(smalls):
            tmp = []
            if not small or small[0] not in d:
                ans.append(tmp)
                continue
            for i in d[small[0]]:
                if big[i:i + len(small)] == small:
                    tmp += [i]
            ans.append(tmp)
        return ans

    # KMP：求子串的问题当然也可以用KMP解决，和LC: 28完全类似，不过这里的KMP匹配到子串后不能停下来，而是要回退
    # 一步`j`，继续循环。设$m$为`smalls`的个数，则复杂度$O(k+m*n)$
    def multiSearch2(self, big: str, smalls: List[str]) -> List[List[int]]:
        ans = [[] for _ in range(len(smalls))]
        for idx, small in enumerate(smalls):
            n = len(small)
            if n == 0:
                continue
            dp = [0] * n
            j = 0
            for i in range(1, n):
                while j and small[j] != small[i]:
                    j = dp[j - 1]
                if small[j] == small[i]:
                    j += 1
                    dp[i] = j
            j = 0
            for i in range(len(big)):
                while j and small[j] != big[i]:
                    j = dp[j - 1]
                if small[j] == big[i]:
                    j += 1
                    if j == n:
                        ans[idx].append(i - n + 1)
                        j = dp[j - 1]
        return ans

    # 前缀树：用所有`small`串构建前缀树，(设`k`为所有`small`串的字符数和则复杂度为$O(k)$)，然后用`big`的所有
    # 后缀子串去匹配(也可以理解为是从big的每个位置作为起点的串)，如果在前缀树里找到了那就保存结果，没找到就从
    # 下一个起点开始，匹配的复杂度为$O(n*max(smalls[i]))$，整体复杂度$O(k+n*max(smalls[i]))$。
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        trie = {}
        for i, small in enumerate(smalls):
            node = trie
            for ch in small:
                if ch not in node:
                    node[ch] = {}
                node = node[ch]
            node['#'] = i
        ans = [[] for _ in range(len(smalls))]
        for i in range(len(big)):
            node = trie
            for ch in big[i:]:
                if ch not in node:
                    break
                node = node[ch]
                if '#' in node:
                    ans[node['#']].append(i)
        return ans

[Arya-03]

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        position=[]
        len_big=len(big)
        if len_big==0:
            for k in range(len(smalls)):
                position.append([])
        elif len(smalls)==0 or smalls==[""]:
            position=[[]]
        else:
            for i in smalls:
                len_small_ele=len(i)
                init_ele=[]
                for j in range(len_big-len_small_ele+1):
                    if big[j:j+len_small_ele]==i:
                        init_ele.append(j)
                position.append(init_ele)
        return (position)

复杂度:O（N*M）

[falconruo]

思路:

暴力法

复杂度分析: 方法一、暴力法

• 时间复杂度: O(N * M)，N为数组big长度, M为数组smalls的长度
• 空间复杂度: O(N), N为数组big长度

代码(C++):

方法一、
class Solution {
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        //if (!big.length() || !smalls.size()) return {};
        vector<vector<int>> res;

        for (string s : smalls) {
            vector<int> pos;
            int len = s.length();

            if (len != 0) {
                for (int i = 0; i < big.length(); ++i)
                    if (s == big.substr(i, len))
                        pos.push_back(i);
            }

            res.push_back(pos);
        }
        return res;
    }
};

[declan92]

思路

1. 遍历small字符串数组,保存至前缀树中;
2. 前缀树中搜索big字符串第一位

java

class Solution {

    public int[][] multiSearch(String big, String[] smalls) {
        int len = smalls.length;
        int[][] ans = new int[len][];
        Trie root = new Trie();
        for(String small : smalls){
            root.insert(small);
        }

        for(int i =0;i<big.length();i++){
            root.search(big.substring(i,big.length()),i);
        }
        for(int i = 0;i<len;i++){
            ans[i] = root.getAns(smalls[i]);
        }
        return ans;
    }

}

class Trie{
    boolean isWord;
    Trie[] chirden;
    List<Integer> res;

    public Trie(){
        chirden = new Trie[26];
        res = new ArrayList();
    }

    public void insert(String word){
        Trie node = this;
        for(int i =0;i<word.length();i++){
            int index = word.charAt(i) - 'a';
            if(node.chirden[index] == null){
                node.chirden[index] = new Trie();
            }
            node = node.chirden[index];
        }
        node.isWord = true;
    }

    public void search(String word,int start){
        Trie node = this;
        for(int i = 0;i<word.length();i++){
            int index = word.charAt(i) - 'a';
            if(node.chirden[index] == null){
                return;
            }
            node = node.chirden[index];
            if(node.isWord){
                node.res.add(start);
            }
        }
    }

    public int[] getAns(String small){
        Trie node = this;
        for(int i = 0;i<small.length();i++){
            int index = small.charAt(i) - 'a';
            node = node.chirden[index];
        }
        List<Integer> list = node.res;
        int[] ans = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}

时间:$O(n+m^2)$,n为small总字符数,m为big长度;
空间:$O(n*k)$,n为small总字符数,k为字符集长度;

[demo410]

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

    class Trie {
        TrieNode root;
        public Trie(String[] words) {
            root = new TrieNode();
            for(String word : words) {
                TrieNode node = root;
                for(char ch : word.toCharArray()) {
                    int i = ch - '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;
        }  
    }

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

[Aobasyp]

思路 字符串匹配

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;

}

时间复杂度：O(N*K) 空间复杂度：O(S)

[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)$

[junbuer]

思路

• 前缀树

  代码

  
  class Trie(object):
  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(object): def multiSearch(self, big, smalls): """ :type big: str :type smalls: List[str] :rtype: 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(m*n)$
+ 空间复杂度：$O(m*k)$

[z1ggy-o]

思路

正好这几天剑指算法也刷到这里。Trie 的使用就是集中在 insert 和 search 中。背一下还是好的。

本题中，利用小词构建 trie，然后依次以 big 的每个字符作为起始点，搜寻匹配即可。

代码

class Solution {
    // 1. use smalls to build trie
    // 2. for each c in big, search until false, count all the words we meet

public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        TrieNode* root = build_trie(smalls);
        vector<vector<int>> ans(smalls.size());

        for (int i = 0; i < big.size(); i++) {
            TrieNode* cur = root;
            for (int j = i; j < big.size(); j++) {
                if (!cur->children[big[j] - 'a'])
                    break;

                cur = cur->children[big[j] - 'a'];
                if (cur->isWord)
                    ans[cur->idx].push_back(i);
                // 不中断，继续搜，可能还有其他的词儿
            }
        }

        return ans;
    }
private:
    struct TrieNode {
        bool isWord;
        int idx;
        vector<TrieNode*> children;

        TrieNode(): isWord{false}, children(26) {}
    };

    TrieNode* build_trie(vector<string>& words)
    {
        TrieNode* root = new TrieNode();
        for (int i = 0; i < words.size(); i++) {
            string& word = words[i];
            TrieNode* cur = root;

            for (auto c: word) {
                if (!cur->children[c - 'a'])
                    cur->children[c - 'a'] = new TrieNode();
                cur = cur->children[c - 'a'];
            }

            cur->isWord = true;
            cur->idx = i;
        }

        return root;
    }
};

复杂度分析

• 时间：O(n^2)，相当于对 big，以它的每一个 char 为起始分割了子字符串，并检查
• 空间：O(m*k), m 是各个小词的长度，k 是小词个数

[pwqgithub-cqu]

class Solution { public: vector<vector> multiSearch(string big, vector& smalls) { //if (!big.length() || !smalls.size()) return {}; vector<vector> res;

    for (string s : smalls) {
        vector<int> pos;
        int len = s.length();

        if (len != 0) {
            for (int i = 0; i < big.length(); ++i)
                if (s == big.substr(i, len))
                    pos.push_back(i);
        }

        res.push_back(pos);
    }
    return res;
}

};

[Hacker90]

class Solution { public: vector multiSearch(string big, vector& smalls) { //if (!big.length() || !smalls.size()) return {}; vector res;

for (string s : smalls) {
    vector<int> pos;
    int len = s.length();

    if (len != 0) {
        for (int i = 0; i < big.length(); ++i)
            if (s == big.substr(i, len))
                pos.push_back(i);
    }

    res.push_back(pos);
}
return res;

} };

[fornobugworld]

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

[zzzpppy]

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

[machuangmr]

代码

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

[charlestang]

思路

1. 把所有短词加入字典树
2. 用 big 的每个后缀去匹配
3. 把结果集插入哈希

代码

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        trie = {}
        # smalls 中的词全部插入字典树，结束标识就用 small 中的 word，方便后续处理
        for word in smalls:
            d = trie
            for char in word:
                if char not in d:
                    d[char] = {}
                d = d[char]
            d['end'] = word

        # 用字典树匹配 big 的后缀，记录匹配成功的所有 small
        def match(s: str):
            res = []
            d = trie
            for char in s:
                if char not in d:
                    break
                d = d[char]
                if 'end' in d:
                    res.append(d['end'])
            return res

        # 遍历 big 的每个后缀
        indice = defaultdict(list)
        n = len(big)
        for i in range(n):
            matches = match(big[i:])
            for word in matches:
                indice[word].append(i)

        ans = []
        for word in smalls:
            ans.append(indice[word])
        return ans

时间复杂度： 假设 smalls 的平均长度是 m，big 的长度是 n，则时间复杂度是 O(m x n)

空间复杂度：假设 smalss 一共有 k 个词，则空间复杂度是 O(k x m)

[hx-code]

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

smalls 中的词全部插入字典树，结束标识就用 small 中的 word，方便后续处理

    for word in smalls:
        d = trie
        for char in word:
            if char not in d:
                d[char] = {}
            d = d[char]
        d['end'] = word

    # 用字典树匹配 big 的后缀，记录匹配成功的所有 small
    def match(s: str):
        res = []
        d = trie
        for char in s:
            if char not in d:
                break
            d = d[char]
            if 'end' in d:
                res.append(d['end'])
        return res

    # 遍历 big 的每个后缀
    indice = defaultdict(list)
    n = len(big)
    for i in range(n):
        matches = match(big[i:])
        for word in matches:
            indice[word].append(i)

    ans = []
    for word in smalls:
        ans.append(indice[word])
    return ans

[for123s]

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

[spacker-343]

思路

把smalls数组插入到前缀树中，用index标识字符串在smalls的位置，然后与不断缩小前缀的big字符串进行匹配

代码

class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < smalls.length; i++) {
            res.add(new ArrayList<>());
        }
        Trie trie = new Trie();
        int idx = 0;
        for (String s : smalls) {
            trie.insert(s, idx);
            idx++;
        }
        int len = big.length();
        for (int i = 0; i < len; i++) {
            trie.search(big.substring(i, len), res, i);
        }
        int[][] ans = new int[smalls.length][];
        for (int i = 0; i < ans.length; i++) {
            int[] temp = new int[res.get(i).size()];
            idx =  0;
            for (int j : res.get(i)) {
                temp[idx++] = j;
            }
            ans[i] = temp;
        }
        return ans;
    }

    class Trie {

        class TrieNode {
            int index = -1;
            TrieNode[] next = new TrieNode[26];
        }

        TrieNode root = new TrieNode();

        public void insert(String s, int i) {
            TrieNode temp = root;
            for (char c : s.toCharArray()) {
                if (temp.next[c - 'a'] == null) {
                    temp.next[c - 'a'] = new TrieNode();
                }
                temp = temp.next[c - 'a'];
            }
            temp.index = i;
        }

        public void search(String s, List<List<Integer>> res, int j) {
            TrieNode temp = root;
            for (char c : s.toCharArray()) {
                if (temp.next[c - 'a'] == null) {
                    break;
                }
                temp = temp.next[c - 'a'];
                if (temp.index != -1) {
                    res.get(temp.index).add(j);
                }
            }
        }
    }
}

复杂度

时间复杂度：O(n^2)

[taojin1992]

/*
0 <= len(big) <= 1000
0 <= len(smalls[i]) <= 1000

If the small doesn't exist in big, no index, []
small and big can be empty

*/

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<Integer>[] startsArrOfList = trie.searchByBigSub(big, smalls.length);
        // process for the output
        int[][] startsArr = new int[startsArrOfList.length][];
        for (int i = 0; i < startsArrOfList.length; i++) {
            startsArr[i] = new int[startsArrOfList[i].size()];
            for (int j = 0; j < startsArrOfList[i].size(); j++) {
                startsArr[i][j] = startsArrOfList[i].get(j);
            }
        }
        return startsArr;
    }

    class Trie {
        TrieNode root = new TrieNode();

        List<Integer>[] searchByBigSub(String big, int numOfSmalls) {
            List<Integer>[] startsOfSub = new List[numOfSmalls];
            for (int i = 0; i < numOfSmalls; i++) {
                startsOfSub[i] = new ArrayList<Integer>();
            }  

            for (int subStart = 0; subStart < big.length(); subStart++) {  
                TrieNode cur = root;           
                for (int subEnd = subStart; subEnd < big.length(); subEnd++) {
                    if (cur.children[big.charAt(subEnd) - 'a'] == null) {
                        break;
                    }
                    cur = cur.children[big.charAt(subEnd) - 'a'];
                    if (cur.isWord) {
                        startsOfSub[cur.id].add(subStart);
                    }
                }
            }
            return startsOfSub;
        }

        void insert(String small, int id) {
            TrieNode cur = root;
            for (int i = 0; i < small.length(); i++) {
                if (cur.children[small.charAt(i) - 'a'] == null) {
                    cur.children[small.charAt(i) - 'a'] = new TrieNode();
                }
                cur = cur.children[small.charAt(i) - 'a'];
            }
            cur.isWord = true;
            cur.id = id;
        }

        class TrieNode {
            TrieNode[] children;
            boolean isWord;
            int id;
            TrieNode() {
                children = new TrieNode[26];
                isWord = false;
                id = -1;
            }
        }
    }
}

[CodingProgrammer]

思路

字典树

代码

class Solution {
    class TrieNode {
        TrieNode[] children;
        boolean isStart;
        public TrieNode() {
            this.children = new TrieNode[26];
            this.isStart = false;
        }
    }

    TrieNode root;

    public int[][] multiSearch(String big, String[] smalls) {
        this.root = new TrieNode();

        // 建立后缀树(以每一个 small 最后一个字符结尾)
        Map<String, List<Integer>> map = new HashMap<>();
        for (String small : smalls) {
            map.put(small, new ArrayList<>());
            insert(small);
        }

        // 在 big 中寻找每一个以 i 为结尾的 small 的开始位置
        for (int i = 0; i < big.length(); i++) {
            search(big, i, map);
        }

        // 搜集结果
        int[][] res = new int[smalls.length][];
        for (int i = 0; i < smalls.length; i++) {
            res[i] = map.get(smalls[i]).stream().mapToInt(Integer::valueOf).toArray();
        }

        return res;
    }

    private void insert(String small) {
        TrieNode node = this.root;
        for (int i = small.length() - 1; i >= 0; i--) {
            int idx = small.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isStart = true;
    }

    private void search(String big, int idxEnd, Map<String, List<Integer>> map) {
        TrieNode node = this.root;
        StringBuilder sb = new StringBuilder();
        // 从 i 出发寻找每一个完整的 small 单词
        for (int i = idxEnd; i >=0 ; i--) {
            int idx = big.charAt(i) - 'a';
            if (node.children[idx] == null) break;
            sb.insert(0, big.charAt(i));
            node = node.children[idx];
            if (node.isStart) {
                map.get(sb.toString()).add(i);
            }
        }
    }
}

复杂度

• 时间复杂度：O(m * n) m 为 smalls 的长度， n 为 big 的长度
• 空间复杂度：O(m * k) m 为 smalls 的长度， k 为 max(len(small))

[tian-pengfei]

class Trie{

public:
    bool isWord;

    int id;

    vector<Trie*> children;

    Trie(){
        id=0;
        isWord = false;
        children.resize(26);
    }

};
class Solution {

    Trie * root;
    //使用smalls构建单词搜索树，用big去匹配，依次去掉开始的字母去匹配
public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {

        root = new Trie();
        int n = smalls.size();

        for (int i = 0; i < n; ++i) {
            insert(i,smalls[i]);
        }
        vector<vector<int>> re(n);
        for (int i = 0; i < big.size(); ++i) {
            Trie *tmp = root;
            for (int j = i; j < big.size(); ++j) {
                char c = big[j];
                c -='a';
                if(tmp->children[c]== nullptr)break;
                tmp = tmp->children[c];
                if(tmp->isWord){
                    re[tmp->id].push_back(i);
                }
            }
        }

        return re;
    }

    void insert(int id, string word){

        Trie *tmp = root;

        for ( auto c: word){
            c-='a';
            if(tmp->children[c]== nullptr){
                tmp->children[c] = new Trie;   
            }
        tmp = tmp->children[c];
        }
        tmp->isWord= true;
        tmp->id = id;
    }

};

[dahaiyidi]

Problem

[面试题 17.17. 多次搜索](https://leetcode-cn.com/problems/multi-search-lcci/)

++

难度中等39

给定一个较长字符串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]]

---

Note

• Trie前缀树的变通使用

---

Complexity

• 时间O：
• 空间O：

---

Python

C++

struct TrieNode{
    int sid; //small 字符串在smalls字符数组中的索引
    TrieNode* next[26];
    TrieNode(){
        sid = -1;
        for(int i = 0; i < 26; i++){
            next[i] = nullptr;
        }
    }
};
class Solution {
private:
    TrieNode* root = new TrieNode();
    // 针对smalls构建前缀树
    void insert(string small_str, int sid){
        TrieNode* node = root;
        for(int i = 0; i < small_str.size(); i++){
            int ind = small_str.at(i) - 'a';
            if(node->next[ind] == nullptr){
                node->next[ind] = new TrieNode();
            }
            node = node->next[ind];
        }
        // 最终退出for循环时, node是small_str最后一个字符所在的node
        node->sid = sid;
    }

    // 在Trie中寻找big子串
    void search(string big_str, vector<vector<int>>& ans, int bid){
        TrieNode* node = root;
        for(int i = 0; i < big_str.size(); i++){
            int ind = big_str.at(i) - 'a';

            // 有small与当前big_str[0, i]一致
            if(node->sid != -1){
                // 到当前位置，small与big_str相同
                ans[node->sid].emplace_back(bid);
            }

            if(node->next[ind] == nullptr){
                return;
            }
            node = node->next[ind];
        }
        // 判断最后一个字符
        if(node->sid != -1){
            // 到当前位置，small与big_str相同
            ans[node->sid].emplace_back(bid);
        }
    }

public:
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
        vector<vector<int>> ans(smalls.size(), vector<int>());
        // 将smalls加入trie
        for(int i = 0; i < smalls.size(); i++){
            if(smalls[i].size() == 0){
                continue;
            }
            insert(smalls[i], i); // 将small字符串和对应的在smalls中的索引加入trie
        }
        // 在trie中不断检索big的子串
        for(int i = 0; i < big.size(); i++){
            string big_str = big.substr(i, big.size() - i);
            search(big_str, ans, i);
        }
        return ans;

    }
};

From : https://github.com/dahaiyidi/awsome-leetcode