# LeetCode: 30. 串联所有单词的子串¶

## 1、题目描述¶

输入：
s = "barfoothefoobarman",
words = ["foo","bar"]



输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]



## 2、解题思路¶

• 首先将所有的索引对应的单词用字典进行标记
• 设单词长度为word_length，所有单词长度为total_length
首先从0开始，0到total_length之间的单词进行统计，使用单个变量进行标记
- negative  表示当前范围中这个单词的待匹配数量为负
- zero      表示当前范围中这个单词的待匹配数量为0
- positive  表示当前范围中这个单词的待匹配数量为正


• 然后从[0,word_length)作为起点进行遍历即可，不断更新三个变量进行判断
from collections import Counter
import copy

class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not words:
return []
if len(set(words)) == 1 and words[0] == "":
return list(range(len(words) + 1))

count = Counter(words)
ans = []
length = len(s)
per_word_length = len(words[0])
total_word_length = per_word_length * len(words)
mapping = {}

for i in range(length - per_word_length + 1):
temp = s[i:i + per_word_length]
if temp in count:
mapping[i] = temp

for start in range(per_word_length):
cur_count = copy.copy(count)
if start + total_word_length <= length:
negative, zero, positive = 0, 0, len(cur_count)
for i in range(start, total_word_length, per_word_length):
if i in mapping:
w = mapping[i]
pre = cur_count[w]
cur_count[w] -= 1
if pre == 1:
positive -= 1
zero += 1
elif pre == 0:
zero -= 1
negative += 1

if zero == len(cur_count):
ans.append(start)

for i in range(start + per_word_length, length, per_word_length):
if i + total_word_length <= length:
before = i - per_word_length
after = i + total_word_length - per_word_length
if before in mapping:
pre = cur_count[mapping[before]]
cur_count[mapping[before]] += 1
if pre == -1:
negative -= 1
zero += 1
elif pre == 0:
zero -= 1
positive += 1
if after in mapping:
pre = cur_count[mapping[after]]
cur_count[mapping[after]] -= 1
if pre == 1:
positive -= 1
zero += 1
elif pre == 0:
zero -= 1
negative += 1
if zero == len(cur_count):
ans.append(i)
else:
break
else:
break

return sorted(ans)