76、最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串 “”。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
题解
分析：理论上的最小子串是T的异构串。我们需要维护部分异构子串。
1、滑动窗口解法
- 遍历t串统计目标串的字符及其数量
- 初始化字符种类数量、左右指针、找到的值
- 初始化窗口，及其窗口区间记录数组
- 遍历s串
- 统计窗口字符
- 判断某个字符是否匹配完成
- 窗口匹配字符数+1
- 窗口包含了全部的t串字符
- 尝试移动左指针，优化窗口
- 右指针++
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
// 统计字串中包含的字符
Map<Character, Integer> dictT = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
int required = dictT.size();
int l = 0, r = 0;
int formed = 0;
// 记录窗口
Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
int[] ans = {-1, 0, 0};
while (r < s.length()) {
char c = s.charAt(r);
int count = windowCounts.getOrDefault(c, 0);
windowCounts.put(c, count + 1);
// 达到目标
if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
formed++;// 统计已记录的不同字符个数
}
// 字符窗口已经统计完毕，进行优化
while (l <= r && formed == required) {
c = s.charAt(l);
if (ans[0] == -1 || r - l + 1 < ans[0]) {
ans[0] = r - l + 1;
ans[1] = l;
ans[2] = r;
}
windowCounts.put(c, windowCounts.get(c) - 1);
// 缩短窗口，找最小子串
if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}
- 优化
增加 List<Pair> 记录下标和字符的最后映射，提高下标检索效率
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
Map<Character, Integer> dictT = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
int required = dictT.size();
// Filter all the characters from s into a new list along with their index.
// The filtering criteria is that the character should be present in t.
List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (dictT.containsKey(c)) {
filteredS.add(new Pair<Integer, Character>(i, c));
}
}
int l = 0, r = 0, formed = 0;
Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
int[] ans = {-1, 0, 0};
// Look for the characters only in the filtered list instead of entire s.
// This helps to reduce our search.
// Hence, we follow the sliding window approach on as small list.
while (r < filteredS.size()) {
char c = filteredS.get(r).getValue();
int count = windowCounts.getOrDefault(c, 0);
windowCounts.put(c, count + 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
formed++;
}
// Try and co***act the window till the point where it ceases to be 'desirable'.
while (l <= r && formed == required) {
c = filteredS.get(l).getValue();
// Save the smallest window until now.
int end = filteredS.get(r).getKey();
int start = filteredS.get(l).getKey();
if (ans[0] == -1 || end - start + 1 < ans[0]) {
ans[0] = end - start + 1;
ans[1] = start;
ans[2] = end;
}
windowCounts.put(c, windowCounts.get(c) - 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}
数组哈希表 7ms
- 初始化 hash表
- 最小子串长度
- 结果子串
- t 串哈希化
- 初始化左右指针
- 遍历s串的每一个字符
- 字符哈希映射统计–
- 字符哈希映射统计 >= 0
- 不匹配字符串总数减一
- 循环，
left < right，t串哈希中不存在左字符（多减了）- 左字符串值哈希++（还原）
- left++
- 找到了子串
count == 0且 当前子串是最短的minlength >= right - left + 1- 更新子串结果
- 返回最小的子串
class Solution {
public String minWindow(String s, String t) {
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
// 用来存储滑动窗口中的值(注意还有小写的)
int[] hash = new int[256];
// 最小子串的长度
int minlength = s.length();
// 最小子串
String results = "";
// t 串哈希化
for (char smallt : tt) {
hash[smallt - '0']++;
}
int left = 0;
int right = 0;
int count = tt.length;
for (; right < ss.length; right++) {
hash[ss[right] - '0']--;// 字符移除
if (hash[ss[right] - '0'] >= 0) {// 总数减一
count--;// 窗口中存在字符，是t的子串
}
// 遍历所有不在字符的case，进行pass
while (left < right && hash[ss[left] - '0'] < 0) {
hash[ss[left] - '0']++;// 加进来，避免遍历到right
left++;
}
// count = 0说明已经覆盖率t串，确保长度最小维护minlength
if (count == 0 && minlength >= right - left + 1) {
minlength = right - left + 1;
results = s.substring(left, right + 1);// 更新符合要求的子串
}
}
return results;
}
}
// 作者：coder_hezi
// 链接：https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-chao-xiang-xi-jie-xi-k/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
