题目难度: 中等

原题链接[1]

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个较长字符串 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 中没有重复字符串。
• 所有出现的字符均为英文小写字母。

题目思考

1. 如何尽可能优化时间复杂度?

解决方案

方案 1

思路

• 分析题目, 一个很容易想到的方案就是使用各个语言提供的字符串 find()函数
• 然后针对每个 small 字符串, 查找它在 big 字符串中所有可能的起点
• 以 Python3 为例, find()可以传入待查找的起点, 并返回从那个起点开始查找到的子串的首个起点, 如果没找到则返回-1
• 这样我们就可以不停循环上述过程, 直到找不到 small 子串为止
• 下面代码有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(NMS): 假设 N 是 big 字符串的长度, M 是 smalls 字符串数组的元素个数, S 是 small 字符串的平均长度; 则外层循环复杂度为 O(M), 内层循环最多需要对每个起点匹配对应的子串, 就是 O(NS), 所以总时间复杂度是 O(NMS)
• 空间复杂度 O(1): 除了结果数组外, 没有使用额外的空间

代码

class Solution:    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:        # 方法1: 语言自带find        res = []        for s in smalls:            res.append([])            # 初始化起点为-1, 因为下面的find逻辑是从i+1开始查找            i = -1            if s != "":                while True:                    # i是上一个查找到的起点, 接下来从i+1开始查, 保证不重复                    i = big.find(s, i + 1)                    if i != -1:                        # 找到了, 追加起点                        res[-1].append(i)                    else:                        # 没找到, 跳出循环                        break        return res

方案 2

思路

• 回顾方案 1, 可以发现它在查找起点时会进行很多重复的匹配, 效率比较低, 有没有更优的方案呢?
• 重新分析题目, 我们可以发现, 某个 small 字符串要想成为 big 的子串, 则它一定是 big 从某个起点开始的前缀
• 所以这里我们可以引入前缀树 trie, 将所有 small 字符串加入 trie 中
• 然后依次遍历 big 的每个起点, 查找从它开始的某个前缀是否已经在 trie 中, 是的话则说明该前缀就是一个 small 字符串
• 这里我们需要对每个节点额外加上一个属性 index, 来代表当前 small 字符串的下标
• 这样在找到一个前缀后, 我们就可以对结果列表对应的下标处追加上当前的 big 起点了
• 下面代码有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(MS+NS): 假设 N 是 big 字符串的长度, M 是 smalls 字符串数组的元素个数, S 是 small 字符串的平均长度; 则插入 trie 的复杂度为 O(MS), 查找起点时, 外层循环复杂度为 O(N), 内层最多遍历 S 层, 复杂度为 O(S), 所以这部分总复杂度为 O(NS)
• 空间复杂度 O(MS): 需要存储 small 字符串列表的所有字符

代码

class Solution:    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:        # 方法2: 逆向思考+trie存small+遍历big起点        class Node:            def __init__(self, c):                self.c = c                # children字典, 存储字符到节点的映射                self.children = {}                # small字符串下标, 初始化为-1, 只有当遍历到small最后一个字符时才赋值, 保证完整性                self.index = -1        n, m = len(big), len(smalls)        root = Node("")        for i, w in enumerate(smalls):            # 将当前字符串加入trie中, 达到终点时记录当前下标            # 因为smalls的字符串都不重复, 所以不存在下标覆盖的情况            cur = root            for c in w:                if c not in cur.children:                    cur.children[c] = Node(c)                cur = cur.children[c]            # 赋值下标, 从root到cur的路径形成了完整的当前small字符串            cur.index = i        # 预生成结果列表        res = [[] for _ in range(m)]        for start in range(n):            # 遍历big的每个起点start            cur = root            i = start            while cur and i < n:                c = big[i]                if c not in cur.children:                    # 当前字符不在trie中, 后面就更不存在有效的small字符串了, 直接退出循环                    break                # 进入下一层                cur = cur.children[c]                i += 1                if cur.index != -1:                    # 当前节点索引不是-1, 说明找到了一个完整的small字符串 (从root一路到cur)                    # 此时需要将结果列表的small下标处追加上当前big的起点start, 表示这个small字符串在start位置处出现                    res[cur.index].append(start)        return res

参考资料

[1]

原题链接: https://leetcode.cn/problems/multi-search-lcci/