class Solution {
public:
string minWindow(string s, string t) {
}
};
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"
示例 2：
输入：s = "a", t = "a" 输出："a"
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 105s 和 t 由英文字母组成进阶：你能设计一个在
o(n) 时间内解决此问题的算法吗？
原站题解
java 解法, 执行用时: 13 ms, 内存消耗: 42.4 MB, 提交时间: 2023-04-22 12:12:32
class Solution {
public String minWindow(String source, String target) {
char[] s = source.toCharArray();
char[] t = target.toCharArray();
// needs是需要的字符和数量，window记录窗口中有效的字符和数量
HashMap<Character, Integer> needs = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
// valid 变量表示窗口中满足 need 条件的字符个数
int valid = 0;
int left = 0, right = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
for(char c : t){
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
while(right < s.length){
// c 是将移入窗口的字符
char c = s[right];
// 扩大窗口
right++;
// 进行窗口内数据的一系列更新
if(needs.containsKey(c)){
window.put(c, window.getOrDefault(c, 0) + 1);
// ⭐注意：两个Integer类型的数据不能直接用< == >判断
if(window.get(c).equals(needs.get(c))){
valid++;
}
}
// 判断左侧窗口是否要收缩
while(valid == needs.size()){
// 在这里更新最小覆盖子串(更新最终结果)
if(right - left < len){
start = left;
len = right - left;
}
// d 是将移要出窗口的字符
char d = s[left];
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if(needs.containsKey(d)){
window.put(d, window.get(d) - 1);
// window窗口内的数据无法满足，不再有效
// ⭐注意：两个Integer类型的数据不能直接用< == >判断
if(window.get(d) < Integer.valueOf(needs.get(d))){
valid--;
}
}
}
}
// 返回最小覆盖子串(使用三目运算使代码简洁)
return len == Integer.MAX_VALUE ? "" : source.substring(start, start + len);
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 15.3 MB, 提交时间: 2023-04-22 12:11:42
class Solution:
def minWindow(self, s: str, t: str) -> str:
need=collections.defaultdict(int)
for c in t:
need[c]+=1
needCnt=len(t)
i=0
res=(0,float('inf'))
for j,c in enumerate(s):
if need[c]>0:
needCnt-=1
need[c]-=1
if needCnt==0: #步骤一：滑动窗口包含了所有T元素
while True: #步骤二：增加i，排除多余元素
c=s[i]
if need[c]==0:
break
need[c]+=1
i+=1
if j-i<res[1]-res[0]: #记录结果
res=(i,j)
need[s[i]]+=1 #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
needCnt+=1
i+=1
return '' if res[1]>len(s) else s[res[0]:res[1]+1] #如果res始终没被更新过，代表无满足条件的结果
golang 解法, 执行用时: 192 ms, 内存消耗: 3 MB, 提交时间: 2023-04-22 12:11:06
func minWindow(s string, t string) string {
ori, cnt := map[byte]int{}, map[byte]int{}
for i := 0; i < len(t); i++ {
ori[t[i]]++
}
sLen := len(s)
len := math.MaxInt32
ansL, ansR := -1, -1
check := func() bool {
for k, v := range ori {
if cnt[k] < v {
return false
}
}
return true
}
for l, r := 0, 0; r < sLen; r++ {
if r < sLen && ori[s[r]] > 0 {
cnt[s[r]]++
}
for check() && l <= r {
if (r - l + 1 < len) {
len = r - l + 1
ansL, ansR = l, l + len
}
if _, ok := ori[s[l]]; ok {
cnt[s[l]] -= 1
}
l++
}
}
if ansL == -1 {
return ""
}
return s[ansL:ansR]
}
java 解法, 执行用时: 164 ms, 内存消耗: 42.5 MB, 提交时间: 2023-04-22 12:10:43
class Solution {
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
int tLen = t.length();
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = -1;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
while (r < sLen) {
++r;
if (r < sLen && ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {
Iterator iter = ori.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
cpp 解法, 执行用时: 168 ms, 内存消耗: 7.7 MB, 提交时间: 2023-04-22 12:10:22
class Solution {
public:
unordered_map <char, int> ori, cnt;
bool check() {
for (const auto &p: ori) {
if (cnt[p.first] < p.second) {
return false;
}
}
return true;
}
string minWindow(string s, string t) {
for (const auto &c: t) {
++ori[c];
}
int l = 0, r = -1;
int len = INT_MAX, ansL = -1, ansR = -1;
while (r < int(s.size())) {
if (ori.find(s[++r]) != ori.end()) {
++cnt[s[r]];
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
}
if (ori.find(s[l]) != ori.end()) {
--cnt[s[l]];
}
++l;
}
}
return ansL == -1 ? string() : s.substr(ansL, len);
}
};