leetcode [面试题17.17] 多次搜索

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个较长字符串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中没有重复字符串。

动态规划，遍历字符串，如果字符串出现在字典中，那么结束处的dp值和前一个dp值相等。

class Solution:
    def multiSearch(self, big: str, smalls: List[str]) -> List[List[int]]:
        ans = [[] for _ in range(len(smalls))]
        for i in range(len(big)):
            for j, s in enumerate(smalls):
                if i + len(s) <= len(big) and big[i: i + len(s)] == s and s != '':
                    ans[j].append(i)
        return ans