• LeetCode每日一题——30. 串联所有单词的子串


    题目

    给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

    注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。

    示例

    示例 1:

    输入:s = “barfoothefoobarman”, words = [“foo”,“bar”]
    输出:[0,9]
    解释: 从索引 0和 9 开始的子串分别是 “barfoo” 和 “foobar” 。 输出的顺序不重要, [9,0] 也是有效答案。

    示例 2:

    输入:s = “wordgoodgoodgoodbestword”, words =
    [“word”,“good”,“best”,“word”]
    输出:[]

    示例 3:

    输入:s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
    输出:[6,9,12]

    提示:

    1 <= s.length <= 104
    s 由小写英文字母组成
    1 <= words.length <= 5000
    1 <= words[i].length <= 30
    words[i] 由小写英文字母组成

    思路

    该题意思是求给定s中能被words中所有字符使用一次可以组成子串的起点下标。

    因为words中字符长度一致,所以想到可以使用滑动窗口,窗口长度为words中字符的长度n。

    并且需要一个哈希表记录words中的字符及出现的次数,因为words中的字符可能出现重复,不能简单使用数组判断是否存在。

    具体方法是,维持这个滑动窗口,判断窗口中的值是否在words中

    • 如果不在,直接左右两端同时+1,窗口整体向右移动一个单位。
    • 如果在,哈希表中对应字符的数量-1,滑动窗口一次向右移动n个单位,直接判断下一个窗口中的字符是否在哈希表中,如果在循环上面步骤,注意:这里最多判断words中的字符长度即可,因为题目要求所有字符都出现且出现一次

    最后判断哈希表中所有的值是否为零即可,若全为零记录这个滑动窗口左指针,若不为零直接左右两端同时+1,窗口整体向右移动,循环以上步骤即可。

    题解

    class Solution:
        def findSubstring(self, s: str, words: List[str]) -> List[int]:
            n = len(words[0])
            #  滑动窗口两侧指针
            l, r = 0, n
            res = []
            temp = {}
            # 哈希表记录字符及数量
            for i in words:
                temp[i] = temp.get(i, 0) + 1
            while r <= len(s):
                ans = copy.copy(temp)
           		# 窗口中字符存在于words
                if s[l:r] in words:
                	# 每次移动n个单位判断
                    for i in range(0, len(words)):
                        index = s[l+i*n:r+i*n]
                        if ans.get(index, 0) != 0:
                            ans[index] -= 1
                        else:
                            break
                if len(set(ans.values())) == 1 and list(ans.values())[0]==0:
                    res.append(l)
                # 窗口整体向右移动
                l += 1
                r += 1
            return res
    
    • 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
  • 相关阅读:
    C语言学习笔记(六):数组(1)
    IP-guard助力能源企业完善终端防泄密措施,保护机密资料安全
    外汇监管机构哪个好?怎么选择?
    深入理解Python中的多线程与多进程编程
    什么是istio?
    3.8、集线器与交换机的区别
    代码层面探索前端性能
    如何才能搭建高质量的在线产品手册呢?
    聊聊 从源码来看ChatGLM-6B的模型结构
    edge 浏览器插件 demo --chatGpt
  • 原文地址:https://blog.csdn.net/m0_52000372/article/details/125423738