【优选算法】（第八篇）
目录
串联所有单词的⼦串（hard）
题目解析
讲解算法原理
编写代码
最⼩覆盖⼦串（hard）
题目解析
讲解算法原理
编写代码
串联所有单词的⼦串（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个字符串s和⼀个字符串数组words。words中所有字符串⻓度相同。
s中的串联⼦串是指⼀个包含words中所有字符串以任意顺序排列连接起来的⼦串。
◦ 例如，如果words=[)ab),)cd),)ef)]，那
么)abcdef)，)abefcd)，)cdabef)，)cdefab)，)efabcd)，和)efcdab)都是串联⼦串。)acdbef)不是串联⼦串，因为他不是任何words排列的连接。
返回所有串联字串在s中的开始索引。你可以以任意顺序返回答案。
⽰例1：
输⼊：s=)barfoothefoobarman),words=[)foo),)bar)]输出：[0,9]
解释：因为words.length==2同时words[i].length==3，连接的⼦字符串的⻓度必须为6。⼦串)barfoo)开始位置是0。它是words中以[)bar),)foo)]顺序排列的连接。
⼦串)foobar)开始位置是9。它是words中以[)foo),)bar)]顺序排列的连接。输出顺序⽆关紧要。返回[9,0]也是可以的。
⽰例2：
输⼊：s=)wordgoodgoodgoodbestword),words=[)word),)good),)best),)word)]输出：[]
解释：因为words.length==4并且words[i].length==4，所以串联⼦串的⻓度必须为16。s中没有⼦串⻓度为16并且等于words的任何顺序排列的连接。
所以我们返回⼀个空数组。
⽰例3：
输⼊：s=)barfoofoobarthefoobarman),words=[)bar),)foo),)the)]输出：[6,9,12]
解释：因为words.length==3并且words[i].length==3，所以串联⼦串的⻓度必须为9。⼦串)foobarthe)开始位置是6。它是words中以[)foo),)bar),)the)]顺序排列的连接。⼦串)barthefoo)开始位置是9。它是words中以[)bar),)the),)foo)]顺序排列的连接。⼦串)thefoobar)开始位置是12。它是words中以[)the),)foo),)bar)]顺序排列的连接。
提⽰：
1<=s.length<=104
1<=words.length<=5000
1<=words[i].length<=30
words[i]和s由⼩写英⽂字⺟组成
讲解算法原理
解法⼀（暴⼒解法）：
算法思路：
如果我们把每⼀个单词看成⼀个⼀个字⺟，问题就变成了找到「字符串中所有的字⺟异位词」。⽆⾮就是之前处理的对象是⼀个⼀个的字符，我们这⾥处理的对象是⼀个⼀个的单词。
编写代码
c++算法代码：
class Solution
{
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ret;
unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
for(auto& s : words) hash1[s]++;
int len = words[0].size(), m = words.size();
for(int i = 0; i < len; i++) // 执⾏ len 次
{
unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
for(int left = i, right = i, count = 0; right + len <= s.size();
right += len)
{
// 进窗⼝ + 维护 count
string in = s.substr(right, len);
hash2[in]++;
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
// 判断
if(right - left + 1 > len * m)
{
// 出窗⼝ + 维护 count
string out = s.substr(left, len);
if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += len;
}
// 更新结果
if(count == m) ret.push_back(left);
}
}
return ret;
}
};java算法代码：
class Solution
{
public List<Integer> findSubstring(String s, String[] words)
{
List<Integer> ret = new ArrayList<Integer>();
// 保存字典中所有单词的频次
Map<String, Integer> hash1 = new HashMap<String, Integer>();
for(String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);
int len = words[0].length(), m = words.length;
for(int i = 0; i < len; i++) // 执⾏次数
{
// 保存窗⼝内所有单词的频次
Map<String, Integer> hash2 = new HashMap<String, Integer>();
for(int left = i, right = i, count = 0; right + len <= s.length();
right += len)
{
// 进窗⼝ + 维护 count
String in = s.substring(right, right + len);
hash2.put(in, hash2.getOrDefault(in, 0) + 1);
if(hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;
// 判断
if(right - left + 1 > len * m)
{
// 出窗⼝ + 维护 count
String out = s.substring(left, left + len);
if(hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
hash2.put(out, hash2.get(out) - 1);
left += len;
}
// 更新结果
if(count == m) ret.add(left);
}
}
return ret;
}
}最⼩覆盖⼦串（hard）
题目解析
1.题目链接：. - 力扣（LeetCode）
2。题目描述
给你⼀个字符串s、⼀个字符串t。返回s中涵盖t所有字符的最⼩⼦串。如果s中不存在涵盖t所有字符的⼦串，则返回空字符串""。
注意：
对于t中重复字符，我们寻找的⼦字符串中该字符数量必须不少于t中该字符数量。如果s中存在这样的⼦串，我们保证它是唯⼀的答案。
⽰例1：
输⼊：s=)ADOBECODEBANC),t=)ABC)输出：)BANC)
解释：
最⼩覆盖⼦串)BANC)包含来⾃字符串t的*A*、*B*和*C*。⽰例2：
输⼊：s=)a),t=)a)输出：)a)
解释：
整个字符串s是最⼩覆盖⼦串。⽰例3:
输⼊:s=)a),t=)aa)输出:""
解释:
t中两个字符*a*均应包含在s的⼦串中，
因此没有符合条件的⼦字符串，返回空字符串。
讲解算法原理
解法（滑动窗⼝+哈希表）：
算法思路：
◦ 研究对象是连续的区间，因此可以尝试使⽤滑动窗⼝的思想来解决。
◦ 如何判断当前窗⼝内的所有字符是符合要求的呢？
我们可以使⽤两个哈希表，其中⼀个将⽬标串的信息统计起来，另⼀个哈希表动态的维护窗⼝内字符串的信息。
当动态哈希表中包含⽬标串中所有的字符，并且对应的个数都不⼩于⽬标串的哈希表中各个字符的个数，那么当前的窗⼝就是⼀种可⾏的⽅案。
算法流程：
a. 定义两个全局的哈希表： 1 号哈希表 hash1 ⽤来记录⼦串的信息， 2 号哈希表 hash2
⽤来记录⽬标串 t 的信息；
b. 实现⼀个接⼝函数，判断当前窗⼝是否满⾜要求：
i. 遍历两个哈希表中对应位置的元素：
• 如果 t 中某个字符的数量⼤于窗⼝中字符的数量，也就是 2 号哈希表某个位置⼤于
1 号哈希表。说明不匹配，返回 false ；
• 如果全都匹配，返回 true 。
主函数中：
a. 先将 t 的信息放⼊ 2 号哈希表中；
b. 初始化⼀些变量：左右指针： left = 0，right = 0 ；⽬标⼦串的⻓度： len =
INT_MAX ；⽬标⼦串的起始位置： retleft ；（通过⽬标⼦串的起始位置和⻓度，我们就能找到结果）
c. 当 right ⼩于字符串 s 的⻓度时，⼀直下列循环：
i. 将当前遍历到的元素扔进 1 号哈希表中；
ii. 检测当前窗⼝是否满⾜条件：
• 如果满⾜条件：
◦ 判断当前窗⼝是否变⼩。如果变⼩：更新⻓度 len ，以及字符串的起始位置
retleft ；
◦ 判断完毕后，将左侧元素滑出窗⼝，顺便更新 1 号哈希表；
◦ 重复上⾯两个过程，直到窗⼝不满⾜条件；
iii. right++ ，遍历下⼀个元素；
d. 判断 len 的⻓度是否等于 INT_MAX ：
i. 如果相等，说明没有匹配，返回空串；
ii. 如果不想等，说明匹配，返回 s 中从 retleft 位置往后 len ⻓度的字符串。
编写代码
c++算法代码：
class Solution
{
public:
string minWindow(string s, string t)
{
int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
int kinds = 0; // 统计有效字符有多少种
for(auto ch : t)
if(hash1[ch]++ == 0) kinds++;
int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
int minlen = INT_MAX, begin = -1;
for(int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
if(++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
while(count == kinds) // 判断条件
{
if(right - left + 1 < minlen) // 更新结果
{
minlen = right - left + 1;
begin = left;
}
char out = s[left++];
if(hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count }
}
if(begin == -1) return "";
else return s.substr(begin, minlen);
}
};java算法代码：
class Solution {
public String minWindow(String ss, String tt) {
char[] s = ss.toCharArray();
char[] t = tt.toCharArray();
int[] hash1 = new int[128]; // 统计字符串 t 中每⼀个字符的频次
int kinds = 0; // 统计有效字符有多少种
for(char ch : t)
if(hash1[ch]++ == 0) kinds++;
int[] hash2 = new int[128]; // 统计窗⼝内每个字符的频次
int minlen = Integer.MAX_VALUE, begin = -1;
for(int left = 0, right = 0, count = 0; right < s.length; right++)
{
char in = s[right];
if(++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
while(count == kinds) // 判断条件
{
if(right - left + 1 < minlen) // 更新结果
{
minlen = right - left + 1;
begin = left;
}
char out = s[left++];
if(hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count }
}
if(begin == -1) return new String();
else return ss.substring(begin, begin + minlen);
}
}