题解 | #最小覆盖子串#
最小覆盖子串
http://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac
题目主要信息：
- 在S字符串中找到包含T字符串所有字符的最小连续子串
- 两个字符串仅包含大小写字母
- 如果S中没有包含T中所有字符的子串，返回空字符串""，若有，则存在唯一最短
举一反三：
学习完本题的思路你可以解决如下题目：
方法：哈希表匹配（推荐使用）
知识点1：滑动窗口
滑动窗口是指在数组、字符串、链表等线性结构上的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。我们在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。
知识点2：哈希表
哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。
思路：
字符串仅包含大小写字母，则字符集是已知且有限的，那这种情况下我们可以考虑快速查找某个元素是否出现过的哈希表——只需要维护一个哈希表，将字符串T中的字符作为key值，初始化时当字符在T中出现一次则对应的value值减1：
for(int i = 0; i < T.length(); i++)
//初始化哈希表都为负数，找的时候再加为正
hash[T.charAt(i)] -= 1;
后续如果在字符串S中找到相应字符就可以将其加回来:
char c = S.charAt(fast);
//目标字符匹配+1
hash[c]++;
然后使用双指针维护滑动窗口，在窗口内，哈希表中value都大于0：
for (int i = 0; i < hash.length; i++) {
if (hash[i] < 0)
return false;
}
return true;
这个窗口内出现了T中所有的字符串，此时可以尝试缩小窗口，因为双指针同步向右遍历，因此缩小窗口只能是缩小左界。
具体做法：
- step 1：建立哈希表，遍历字符串T，统计各个字符出现的频率，频率计为负数。
- step 2：依次遍历字符串S，如果匹配则将哈希表中的相应的字符加1。
- step 3：在遍历过程中维护一个窗口，如果哈希表中所有元素都大于0，意味着已经找全了，则窗口收缩向左移动，找最小的窗口，如果不满足这个条件则窗口右移继续匹配。窗口移动的时候需要更新最小窗口，以取得最短子串。
- step 4：如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串即可。
- step 5：最后使用字符串截取函数，截取刚刚记录下的窗口即可得到符合条件的最短子串。
图示：
Java代码实现：
import java.util.*;
public class Solution {
//检查是否有小于0的
boolean check(int[] hash) {
for (int i = 0; i < hash.length; i++) {
if (hash[i] < 0)
return false;
}
return true;
};
public String minWindow (String S, String T) {
int cnt = S.length() + 1;
//记录目标字符串T的字符个数
int[] hash = new int[128];
for(int i = 0; i < T.length(); i++)
//初始化哈希表都为负数，找的时候再加为正
hash[T.charAt(i)] -= 1;
int slow = 0, fast = 0;
//记录左右区间
int left = -1, right = -1;
for(; fast < S.length(); fast++){
char c = S.charAt(fast);
//目标字符匹配+1
hash[c]++;
//没有小于0的说明都覆盖了，缩小窗口
while(check(hash)){
//取最优解
if(cnt > fast - slow + 1){
cnt = fast - slow + 1;
left = slow;
right = fast;
}
c = S.charAt(slow);
//缩小窗口的时候减1
hash[c]--;
//窗口缩小
slow++;
}
}
//找不到的情况
if(left == -1)
return "";
return S.substring(left, right + 1);
}
}
C++代码实现：
class Solution {
public:
//检查是否有小于0的
bool check(unordered_map<char, int> &hash) {
for (auto iter = hash.begin(); iter != hash.end(); iter++) {
if (iter->second < 0)
return false;
}
return true;
}
string minWindow(string S, string T) {
int cnt = S.length() + 1;
//记录目标字符串T的字符个数
unordered_map<char, int> hash;
for(int i = 0; i < T.length(); i++)
//初始化哈希表都为负数，找的时候再加为正
hash[T[i]] -= 1;
int slow = 0, fast = 0;
//记录左右区间
int left = -1, right = -1;
for(; fast < S.length(); fast++){
char c = S[fast];
//目标字符匹配+1
if(hash.count(c))
hash[c]++;
//没有小于0的说明都覆盖了，缩小窗口
while(check(hash)){
//取最优解
if(cnt > fast - slow + 1){
cnt = fast - slow + 1;
left = slow;
right = fast;
}
char c = S[slow];
if(hash.count(c))
//缩小窗口的时候减1
hash[c]--;
//窗口缩小
slow++;
}
}
//找不到的情况
if (left == -1)
return "";
return string(S.begin() + left, S.begin() + (right + 1));
}
};
Python实现代码：
class Solution:
#检查是否有小于0的
def check(self, hash:dict()):
for key, value in hash.items():
if value < 0:
return False
return True
def minWindow(self , S: str, T: str) -> str:
cnt = len(S) + 1
#记录目标字符串T的字符个数
hash = dict()
for i in range(len(T)):
if T[i] in hash:
#初始化哈希表都为负数，找的时候再加为正
hash[T[i]] -= 1
else:
hash[T[i]] = -1
slow = 0
fast = 0
left = -1
#记录左右区间
right = -1
while fast < len(S):
c = S[fast]
#目标字符匹配+1
if c in hash:
hash[c] += 1
#没有小于0的说明都覆盖了，缩小窗口
while (Solution.check(self, hash)) :
#取最优解
if cnt > fast - slow + 1:
cnt = fast - slow + 1
left = slow
right = fast
c = S[slow]
if c in hash:
#缩小窗口的时候减1
hash[c] -= 1
#窗口缩小
slow += 1
fast += 1
#找不到的情况
if left == -1:
return ""
return S[left:right+1]
复杂度分析：
- 时间复杂度：，其中C为T字符串的字符集大小，本题中为52个字母，为字符串S的长度，为字符串T的长度
- 空间复杂度：，哈希表长度不会超过字符串T的字符集大小
