# 【基础篇 - Day 23】 2020-11-23 - 30. 串联所有单词的子串
# 题目描述
# 入选理由
- hashtable 用于空间换时间
# 题目描述
给定一个字符串 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"] 输出：[]来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
# 解法一
# 时空复杂度
时间复杂度：O(n*k) s.length * words.length
空间复杂度: O(n) 2 个 Map 的空间 N 最大为 words.length
今天的好难，一开始就想 用一个 wordLength 循环出来 然后条件删减把自己绕晕了，要循序渐进啊。
var findSubstring = function (s, words) {
const wordLength = words[0].length
const res = []
let wordMap = new Map()
for (let i = 0; i < words.length; i++) {
const newVal = (wordMap.get(words[i]) || 0) + 1
wordMap.set(words[i], newVal)
}
for (let i = 0; i < (s.length - wordLength + 1); i++) {
let map = new Map()
let num = 0
while (num < words.length) {
const word = s.substring(i + num * wordLength, i + (num + 1) * wordLength);
if (words.includes(word)) {
const newVal = (map.get(word) || 0) + 1
map.set(word, newVal)
if (newVal > wordMap.get(word)) {
break;
}
} else {
break;
}
num++
}
if (num == words.length) res.push(i)
}
return res
};