Skip to content

17.17. Multi Search

Description

Given a string band an array of smaller strings T, design a method to search b for each small string in T. Output positions of all strings in smalls that appear in big, where positions[i] is all positions of smalls[i].

Example: 


Input: 

big = "mississippi"

smalls = ["is","ppi","hi","sis","i","ssippi"]

Output:  [[1,4],[8],[],[3],[1,4,7,10],[5]]

Note:

  • 0 <= len(big) <= 1000
  • 0 <= len(smalls[i]) <= 1000
  • The total number of characters in smalls will not exceed 100000.
  • No duplicated strings in smalls.
  • All characters are lowercase letters.

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Trie:
    def __init__(self):
        self.idx = -1
        self.children = [None] * 26

    def insert(self, word, i):
        node = self
        for c in word:
            idx = ord(c) - ord('a')