feat: azl397985856#30

lucifer · lucifer · commit bbf0abf43a4e · 2020-01-19T19:18:32.000+08:00
diff --git a/README.md b/README.md
@@ -241,10 +241,11 @@ leetcode 题解，记录自己的 leetcode 解题之路。
 
 #### 困难难度
 
-- [0004.median-of-two-sorted-array](./problems/4.median-of-two-sorted-array.md) 🆕
+- [0004.median-of-two-sorted-array](./problems/4.median-of-two-sorted-array.md)
 - [0023.merge-k-sorted-lists](./problems/23.merge-k-sorted-lists.md)
 - [0025.reverse-nodes-in-k-group](./problems/25.reverse-nodes-in-k-groups-cn.md) 🆕
-- [0032.longest-valid-parentheses](./problems/32.longest-valid-parentheses.md) 🆕
+- [0030.substring-with-concatenation-of-all-words](./problems/30.substring-with-concatenation-of-all-words.md)
+- [0032.longest-valid-parentheses](./problems/32.longest-valid-parentheses.md)
 - [0042.trapping-rain-water](./problems/42.trapping-rain-water.md)
 - [0124.binary-tree-maximum-path-sum](./problems/124.binary-tree-maximum-path-sum.md)
 - [0128.longest-consecutive-sequence](./problems/128.longest-consecutive-sequence.md)
diff --git a/problems/30.substring-with-concatenation-of-all-words.md b/problems/30.substring-with-concatenation-of-all-words.md
@@ -0,0 +1,75 @@
+## 题目地址（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 中的字符串都是等长的，因此编码上也会比较简单。
+
+1. 我们的目标状态是 Counter(words)，即对 words 进行一次计数。
+2. 我们只需从头开始遍历一次数组，每次截取 word 长度的字符，一共截取 words 长度次即可。
+3. 如果我们截取的 Counter 和 Counter(words)一致，则加入到 res
+4. 否则我们继续一个指针，继续执行步骤二
+5. 重复执行这个逻辑直到达到数组尾部
+
+## 关键点解析
+
+- Counter
+
+## 代码
+
+- 语言支持：Python3
+
+```python
+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 res
+```
