(难度Hard) Problem 30. Substring with Concatenation of All Words (母串匹配多串)

### 链接

https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Hard

### 题干

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

### 样例

Example 1:

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

Example 2:

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

### 题解

#### 解法一 暴力对比

def match(s, words):
l = len(s)
m = len(words[0])
# 词库里单词数量
words_cnt = 0
# 构建单词库
for word : words:
if word not in voca:
voca[word] = 0
voca[word]++
words_cnt++
for i in range(l):
j = i
# 存储当前放入的单词
cur = {}
# 当前放入的单词数
finish = 0
while j < l:
# 提取当前位置的子串
word = s.substr(j, m)
# 如果出现在词库当中，并且数量没有超过
if word in voca and voca[word] > cur[word]:
cur[word]++;
finish++
# 判断是否所有单词都已经放入
if finish == words_cnt:
ans.append(i)
break
j += m


class Solution {
public:
vector findSubstring(string s, vector& words) {
vector vt;
int l = s.size();
if (l==0 || words.size() == 0) return vt;
int m = words[0].size();

    map<string, int> mp;
int wordsCnt = 0;
for (string str : words) {
if (mp.count(str) == 0) mp[str] = 0;
mp[str]++;
wordsCnt++;
}

for (int i = 0; i < l; i++) {
map<string, int> cur;
int wc = 0;
for (int j = i; j < l; j+= m) {
string sub = s.substr(j, m);
if (mp.count(sub) && cur[sub] < mp[sub]) {
cur[sub] ++;
wc++;
}else {
cur.clear();
break;
}`