目录

串联所有单词的⼦串（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);
 }
}