0%

### 题目描述

You are given a string `s` and an array of strings `words` of the same length. Return all starting indices of substring(s) in `s` that is a concatenation of each word in `words` exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

### 例子

#### 例子 1

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively.
The output order does not matter, returning [9,0] is fine too.

#### 例子 2

Input: s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
Output: []

#### 例子 3

Input: s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
Output: [6,9,12]

### Constraints

• `1 <= s.length <= 10^4`
• `s` consists of lower-case English letters.
• `1 <= words.length <= 5000`
• `1 <= words[i].length <= 30`
• `words[i]` consists of lower-case English letters.

### 解题思路

• 首先通过哈希表 `record``words` 中每个单词的出现次数进行记录
• 检查 `s` 中所有长度 `words.size() * words[0].length()` 的子串 （用滑动窗口）
• 对每一个滑动窗口也建立一个哈希表 `cur_record` 中按照 `words[0].length()` 为步长进行遍历取词 `word`，对每一个 `word` 进行检查，如果 `cur_record[word] > record[word]` 则表示出现了不在 `words` 中的单词直接跳出即可
• 如果中间一直没有跳出直到滑动窗口的末尾自然退出循环，则表示所有 `word` 都在 `words` 里，将当前起始坐标添加至结果中

• 首先判断 `s.length() >= words.size() * words[0].length()`，如果不满足可以直接返回空集
• 遍历 `s` 的时候也不必遍历到末尾，直到 `s.length() - words.size() * words[0].length()` 即可

• 时间复杂度: O(mn)
• 空间复杂度: O(n)

GitHub 代码同步地址： 30.SubstringWithConcatenationOfAllWords.cpp

GitHub: Leetcode-C++-Solution