滑动窗口——串联所有单词的子串
一.题目描述
30. 串联所有单词的子串 - 力扣（LeetCode）
二.题目解析
题目前提：s是一个字符串，words是一个字符串数组，里面所有的字符串的长度都是相等的。
题目要求：找到s中的一段连续的子串，该子串是由words中的所有字符串随机排列组合起来的，但是每一个字符串内部的顺序是不变的。然后返回该子串的起始位置即可。
三.算法原理
3.1问题转化
因为words中的每一个字符串都是一样长的，所以我们可以将s字符串进行划分，划分成与words中字符串一样长的形式：
然后我们将words中的两个字符串看作两个字符，那么s中的字符串也可以根据分组看成若干字符，这时，该题就转换成了昨天的那道题——找出所有的异位词，找出一个子区间，是由words组成的即可。
所以这道题我们也可以使用滑动窗口来解决问题。
3.2滑动窗口
在使用滑动窗口之前，我们还要对一些细节进行分析：
细节1：
我们刚才划分是从首位置开始划分的，但是答案也可能这样分布：
所以我们要根据开始位置的不同，进行多次滑动窗口的过程。根据示例的分析，我们需要进行len次滑动窗口(len指words中每一个单词的长度) ，第len+1次滑动窗口就和第一个次一样了。
细节2：
我们这次哈希表里面存的就不再是字符了，而是字符串。所以我们要用容器unordered_map来实现。
细节3：
进窗口的时候，我们就不再是一次进一个元素了，而是进一段子区间。我们可以使用substr函数来获取子区间，该子区间的长度就是words中每一个单词的长度
对于这个示例就是将right后面的3个字符作为字符串插入到哈希表中。
细节4：
判断的逻辑，当子区间的长度大于words所有字符的和的时候就需要出窗口了，但是我们这里没有必要用子区间的所有长度与words总长度比较，只需用right-left+1与总长度比较即可。
细节5：
出窗口的时候，我们让left后面的len个字符出窗口，而不是一个，与进窗口一致。
细节6：
left和right不再一次走一步，因为我们要将一段区间插入到哈希表中，所有left和right每次走len步。
四.代码实现
// C++
// 写法一：
vector<int> ret;
int len = words[0].size();
int n = words.size();
if (s.size() < len * n)
return ret;
unordered_map<string, int> mp_w;
for (auto& e : words) mp_w[e]++;
for (int i = 0; i < len; ++i)
{
unordered_map<string, int> mp_s;
for (int l = i, r = i, count = 0; r + len <= s.size(); r += len)
{
// 进窗口 + 维护count
string s_in = s.substr(r, len);
mp_s[s_in]++;
if (mp_s[s_in] <= mp_w[s_in]) count++;
// 判断
if (r - l + 1 > len * n)
{
// 出窗口 + 维护count
string s_out = s.substr(l, len);
if (mp_s[s_out] <= mp_w[s_out]) count--;
mp_s[s_out]--;
l += len;
}
//更新结果
if (count == n) ret.emplace_back(l);
}
}
return ret;
// 写法二：
vector<int> ret;
int n = words.size(); // words中有几个单词
int len = words[0].size(); // 每个单词的长度
if (s.size() < len * n)
return ret;
unordered_map<string, int> mp_w;
for (auto e : words) mp_w[e]++;
int i = 0;
while (i < len)
{
unordered_map<string, int> mp_s;
int count = 0;
for (int left = i, right = i; right < s.size();)
{
// 进窗口
if (right + len > s.size()) break;
right += len;
string s_in(s.begin() + right - len, s.begin() + right);
mp_s[s_in]++;
if (mp_s[s_in] <= mp_w[s_in]) count++;
// 判断
if (right - left > len * n)
{
string s_out(s.begin() + left, s.begin() + left + len);
if (mp_s[s_out] <= mp_w[s_out]) count--;
mp_s[s_out]--;
left += len;
}
//更新结果
if (count == n) ret.emplace_back(left);
}
++i;
}
return ret;# python
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
ret = [] # 返回列表
cnt_w = Counter() # 记录words中单词的频次
for e in words:
cnt_w[e]+=1
n,Len = len(words),len(words[0]) # words中单词的个数，以及长度
for i in range(0,Len):
cnt_s = Counter() # 窗口中单词的频次
r,l,count = i,i,0
while r+Len <= len(s):
# 进窗口 + 维护 count
s_in = s[r:r+Len]
cnt_s[s_in] += 1
if cnt_s[s_in] <= cnt_w[s_in]:
count+=1
# 判断
if r-l+1>n*Len:
# 出窗口 + 维护 count
s_out = s[l:l+Len]
if cnt_s[s_out] <= cnt_w[s_out]:
count -= 1
cnt_s[s_out] -= 1
l += Len
# 更新结果
if count == n:
ret.append(l)
r += Len
return ret