题目地址(30. 串联所有单词的子串)
https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/description/
题目描述
给定一个字符串 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"]
输出:[]
思路
本题是要我们找出 words 中所有单词按照任意顺序串联
形成的单词中恰好出现在 s 中的索引,因此顺序是不重要的。换句话说,我们只要统计每一个单词的出现情况即可。以题目中 s = "barfoothefoobarman", words = ["foo","bar"] 为例。 我们只需要统计 foo 出现了一次,bar 出现了一次即可。我们只需要在 s 中找到同样包含一次 foo 和一次 bar 的子串即可。由于 words 中的字符串都是等长的,因此编码上也会比较简单。
- 我们的目标状态是 Counter(words),即对 words 进行一次计数。
- 我们只需从头开始遍历一次数组,每次截取 word 长度的字符,一共截取 words 长度次即可。
- 如果我们截取的 Counter 和 Counter(words)一致,则加入到 res
- 否则我们继续一个指针,继续执行步骤二
- 重复执行这个逻辑直到达到数组尾部
关键点解析
- Counter
代码
- 语言支持:Python3
from collections import Counter class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: if not s or not words: return [] res = [] n = len(words) word_len = len(words[0]) window_len = word_len * n target = Counter(words) i = 0 while i < len(s) - window_len + 1: sliced = [] start = i for _ in range(n): sliced.append(s[start:start + word_len]) start += word_len if Counter(sliced) == target: res.append(i) i += 1 return resLeetCode题解1297.maximum-number-of-occurrences-of-a-substring
题目地址(1297. 子串的最大出现次数) https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 题目描述 给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数: 子串中不同字母的数目必须小于等于 maxLetters 。 子串的…
LeetCode题解201.bitwise-and-of-numbers-range题目地址 https://leetcode.com/problems/bitwise-and-of-numbers-range/description/ 题目描述 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbe…
LeetCode题解200.number-of-islands题目地址 https://leetcode.com/problems/number-of-islands/description/ 题目描述 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by …
LeetCode题解238.product-of-array-except-self题目地址 https://leetcode.com/problems/product-of-array-except-self/description/ 题目描述 Given an array nums of n integers where n > 1, return an array output such that output[i] is eq…
LeetCode题解1218.longest-arithmetic-subsequence-of-given-difference题目地址 https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/ 题目描述 给你一个整数数组 arr 和一个整数 difference,请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列,并返回其中最长的等差子序…