# 30.substring-with-concatenation-of-all-words-cn

## 题目地址

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

## 题目描述

``````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: []``````

## 思路

#### 解法一 - 暴力

1. 如果当前单词不在单词数组中,那么以当前字符开头的子串不可能满足情况, 提前结束, 往后移动到下一个字符的子串.

2. 如果当前单词个数超过单词数组, 也不可能满足, 结束, 往后移动到下一个

3. 满足的单词的数量(`count`)加`1`.

4. 比较满足的单词数量`(count == wordNum)`, 满足, 记录下当前下标(`index`), 移动到下一个字符

5. 每次移动第二个HashMap清空, 重新计算

``````s = "barfoothefoobarman"
words = ["foo", "bar"]

Words Map = {[foo:1], [bar:1]}
i=0
子串 Map = {}
| b a r f o o t h e f o o b a r m a n
当前子串: "barfoo", 满足条件, res=[0]
i=1
子串 Map = {}
b | a r f o o t h e f o o b a r m a n
当前子串: "arfoot", 不满足条件, 退出, 移到下一个, res=[0]
i=2
子串 Map = {}
b a | r f o o t h e f o o b a r m a n
当前子串: "rfooth", 不满足条件, 退出, 移到下一个, res=[0]
.
.
.
i=9
子串 Map = {}
b a r f o o t h e | f o o b a r m a n
当前子串: "foobar", 满足条件, res=[0, 9]
.
.
.
i=13, 退出, 剩余子串长度不满足. res=[0, 9]``````

### 解法二

1. 当面单词不满足(不在给定单词数组(`words`)中).

2. 当面单词出现在单词数组(`words`)中,但个数超过给定的个数

3. 往后移动的过程,不需要每次都清空`HashMap`, 造成重复计算, 浪费资源.

## 代码 （Java/Python3）

``````class ConcateSubstringWithAllWords {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if (s == null || words == null || s.length() < words.length || words.length == 0) return res;
Map<String, Integer> wordsMap = new HashMap<>();
for (String w : words) {
wordsMap.put(w, wordsMap.getOrDefault(w, 0) + 1);
}
int len = s.length();
int wordNum = words.length;
int wordLen = words[0].length();
if (len < wordNum * wordLen) return res;
for (int i = 0; i < len - wordNum * wordLen + 1; i++) {
Map<String, Integer> subMap = new HashMap<>();
int currCount = 0;
while (currCount < wordNum) {
String currWord = s.substring(currCount * wordLen + i, (currCount + 1) * wordLen + i);
if (!wordsMap.containsKey(currWord)) break;
subMap.put(currWord, subMap.getOrDefault(currWord, 0) + 1);
if (subMap.get(currWord) > wordsMap.get(currWord)) break;
currCount++;
}
if (currCount == wordNum) {
}
}
return res;
}
}``````

``````class ConcateSubstringWithAllWords {
public static List<Integer> findSubstring2(String s, String[] words) {
// basic cases
if (s == null || words == null || s.length() < words.length || words.length == 0) return res;
List<Integer> res = new ArrayList<>();
final Map<String, Integer> wordsMap = new HashMap<>();
for (final String word : words) {
wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
}
final int len = s.length();
final int wordNum = words.length;
final int wordLen = words[0].length();
for (int i = 0; i < wordLen; i++) {
int l = i, count = 0;
final Map<String, Integer> subMap = new HashMap<>();
for (int r = i; r <= len - wordLen; r += wordLen) {
final String word = s.substring(r, r + wordLen);
// 1. 不满足条件,直接跳到单词后面, 清空map
if (!wordsMap.containsKey(word)) {
subMap.clear();
count = 0;
l = r + wordLen;
continue;
}
subMap.put(word, subMap.getOrDefault(word, 0) + 1);
if (subMap.get(word) <= wordsMap.get(word)) {
count++;
} else {
// 2. 满足条件, 当时个数超过, 那么往前移动直到个数满足的index
while (subMap.get(word) > wordsMap.get(word)) {
final String first = s.substring(l, l += wordLen);
subMap.put(first, subMap.getOrDefault(first, 0) - 1);
if (subMap.get(first) < wordsMap.getOrDefault(first, 0)) {
count--;
}
}
}
if (count == wordNum) {
count--;
final String first = s.substring(l, l += wordLen);
subMap.put(first, subMap.get(first) - 1);
}
}
}
return res;
}
}``````

Python code from @sunboman

``````from typing import List
import collections

class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words:
return []
w_num = len(words)
w_len = len(words[0])
w_count = collections.Counter(words)
res = []
for i in range(w_len):
temp_count = collections.defaultdict(int)
left = i
for right in range(i, len(s) - w_len + 1, w_len):
temp_word = s[right: right + w_len]
if w_count[temp_word] > 0:
temp_count[temp_word] += 1
while temp_count[temp_word] > w_count[temp_word]:
temp_count[s[left: left + w_len]] -= 1
left += w_len
if right + w_len - left == w_num * w_len:
res.append(left)
temp_count[s[left: left + w_len]] -= 1
left += w_len
else:
left = right + w_len
temp_count.clear()
return res``````

## 相似题目

Minimum Window Substring

Last updated