题目

题目来源：力扣（LeetCode）

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

思路分析

  1. 通过smalls构建Trie树，然后遍历big字符串，在前缀树中寻找匹配项。
  2. 找到完整字符则将当前的「索引」添加到结果集，其中last为结果集的index。
  3. 继续向下找，直到匹配不到，big循环完毕
  4. 如果未能找到则break掉，进入下一个字符的循环。
  1. function TreeNode(val) {
  2.   this.val = val || null
  3.   this.children = {}
  4. }
  5. /**
  6. * @param {string} big
  7. * @param {string[]} smalls
  8. * @return {number[][]}
  9. */
  10. var multiSearch = function (big, smalls) {
  11.   // 结果集
  12.   const res = smalls.map(() => [])
  13.   if (!big) {
  14.     return res
  15.   }
  17.   // 构造字典树
  18.   let Tree = new TreeNode()
  19.   let now;
  20.   smalls.forEach((small, index) => {
  21.     now = Tree;
  22.     for (let i = 0; i < small.length; i++) {
  23.       if (!now.children[small[i]]) {
  24.         now.children[small[i]] = new TreeNode(small[i])
  25.       }
  26.       now = now.children[small[i]]
  27.     }
  28.     now.children['last'] = index
  29.   })
  31.   // 遍历 big 字符串，在字典树中查找匹配项
  32.   for (let i = 0; i < big.length; i++) {
  33.     let now = Tree;
  34.     for (let j = i; j < big.length; j++) {
  35.       if (!now.children[big[j]]) {
  36.         break
  37.       }
  38.       now = now.children[big[j]]
  39.       if (now.children.last !== undefined) {
  40.         res[now.children.last].push(i)
  41.       }
  42.     }
  43.   }
  44.   return res
  45. };