【Day 46 】2021-10-25 - 76. 最小覆盖子串 #63
Comments
思路:这题与昨天打卡的 438. 找到字符串中所有字母异位词 的解法有点像。 方法: 滑动窗口 + 哈希表在字符串s中维护一个滑动窗口, 窗口有start 和end两个指针。 如果当前窗口子串包含t中的所有字符且更短, 就更新result。 代码:实现语言: C++ 注: 扩展ASCII码(EXTENDED_ASCII)字符集包含256个字符，大写A的ASCII码是65, 小写z的ASCII码是122。所以, 用数组模拟哈希表时, 大小用256足够了。 class Solution {
public:
string minWindow(string s, string t) {
vector<int> tMap(256); // 字符串t中的字母频次表, 用数组模拟哈希表
for (int i=0; i < t.size(); i++)
tMap[t[i]]++;
int count = t.size(); // 待匹配的字符的数量
vector<int> sMap(256); // 滑动窗口中的字母频次表, 用数组模拟哈希表
int left = -1; // 记录结束时滑动窗口的start、end
int right = -1;
int start = 0;
int minLen = INT_MAX;
for (int i = 0; i < s.size(); i++) /* 循环变量i即为滑动窗口的end */
{
char ch = s[i];
sMap[ch]++;
if (sMap[ch] <= tMap[ch]) /* 匹配上了一个待匹配字符, 待匹配字符的数量可以-1 */
count--;
while (start <= i && count == 0) /* start需要满足边界条件, 如果当前窗口恰好包含字符串t中所有的字符, 需要移动指针试试看有没有更短的 */
{
char h = s[start];
sMap[h]--; /* 从滑动窗口丢掉一个字符串s中此时start位置的字符h(head), 如果发现sMap中字符h的数量不够了, 则待匹配字符才数量+1 */
if (sMap[h] < tMap[h]) count++;
if (count > 0) /* 此时start还没移动, count出现第一次>0 的位置即表示出现新的符合题意的窗口 */
{
if (minLen > i - start + 1) /* 如果出现更短的窗口, 更新一下相关数据 */
{
left = start;
right = i;
minLen = right - left + 1;
}
}
start++;
}
}
if (left == -1) return "";
return s.substr(left, right - left + 1);
}
};复杂度分析
|
思路关键点代码
C++ Code: class Solution {
public:
int query_idx(char c)
{
if(c>='a'&&c<='z')
return c-'a';
return c-'A'+26;
}
string minWindow(string s, string t) {
if(s.size()<t.size())
return {};
vector<int> c_t(52,0);
for(int i=0;i<t.size();i++)
c_t[query_idx(t[i])]++;
string res=s+'a';
int l=0, r=0;
vector<int> c_s(52,0);
int len_ = 0;
while(r<s.size())
{
int idx_r = query_idx(s[r]);
c_s[idx_r]++;
if(c_s[idx_r]<=c_t[idx_r])
{
len_++;
while(len_==t.size())
{
if(r-l+1<res.size())
res = s.substr(l,r-l+1);
int idx_l = query_idx(s[l]);
c_s[idx_l]--;
if(c_s[idx_l]<c_t[idx_l])
len_--;
++l;
}
}
++r;
}
if(res.size()==s.size()+1)
return {};
return res;
}
};
复杂度分析 令 n 为数组长度。
|
思路
关键点代码
C++ Code: class Solution {
public:
string minWindow(string s, string t) {
vector<int> trecord(256,0);
vector<int> srecord(256,0);
for(int i =0; i< t.size(); i++)
{
trecord[t[i]]++;
}
int left =0;
int right =0;
int count =0;
string ret;
int retIndex = INT_MAX;
while(right<s.size())
{
int index = s[right] ;
srecord[index]++;
if(trecord[index]> 0 && srecord[index]<=trecord[index])
{
count++;
}
// shink window
while(count == t.size())
{
if((right-left+1)<retIndex)
{
retIndex = right - left+1;
ret = s.substr(left, retIndex);
}
int leftIndex = s[left] ;
srecord[leftIndex]--;
if(srecord[leftIndex]<trecord[leftIndex])
{
count--;
}
left++;
}
right++;
}
return ret;
}
};
|
思路：1. 用长度为128的数组记录字符出现的次数2. 滑窗代码部分：class Solution {
public String minWindow(String s, String t) {
int[] map = new int[128];
for (char ch : t.toCharArray()) map[ch] ++;
int tLen = t.length();
int left = 0;
int right = 0;
int win = Integer.MAX_VALUE;
int str = 0; // t开始的位置
while (right < s.length()) {
if (map[s.charAt(right ++)] -- > 0) tLen --;
// 如果全覆盖
while (tLen == 0) {
// 更新更小的窗口
if (right - left < win) {
win = right - left;
str = left;
}
if (map[s.charAt(left ++)] ++ == 0) tLen ++;
}
}
if (win != Integer.MAX_VALUE) return s.substring(str, str + win);
return "";
}
}复杂度：Time: O(N)Space: O(1) |
|
Sliding window. class Solution:
def minWindow(self, s: str, t: str) -> str:
l, counter, N, ct = 0, Counter(), len(s), Counter(t)
k = 0
ret, rs = inf, ""
for r in range(N):
counter[s[r]] += 1
if s[r] in t and counter[s[r]] == ct[s[r]]:
k += 1
while k == len(ct):
if r - l + 1 < ret:
rs = s[l:r+1]
ret = min(r - l + 1, ret)
counter[s[l]] -= 1
if s[l] in t and counter[s[l]] == ct[s[l]]-1:
k -= 1
l += 1
return rs |
题目地址(76. 最小覆盖子串)https://leetcode-cn.com/problems/minimum-window-substring/ 题目描述前置知识公司
思路关键点代码
Java Code: class Solution {
public String minWindow(String s, String t) {
if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
return "";
}
//维护两个数组，记录已有字符串指定字符的出现次数，和目标字符串指定字符的出现次数
//ASCII表总长128
int[] need = new int[128];
int[] have = new int[128];
//将目标字符串指定字符的出现次数记录
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
//分别为左指针，右指针，最小长度(初始值为一定不可达到的长度)
//已有字符串中目标字符串指定字符的出现总频次以及最小覆盖子串在原字符串中的起始位置
int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0;
while (right < s.length()) {
char r = s.charAt(right);
//说明该字符不被目标字符串需要，此时有两种情况
// 1.循环刚开始，那么直接移动右指针即可，不需要做多余判断
// 2.循环已经开始一段时间，此处又有两种情况
// 2.1 上一次条件不满足，已有字符串指定字符出现次数不满足目标字符串指定字符出现次数，那么此时
// 如果该字符还不被目标字符串需要，就不需要进行多余判断，右指针移动即可
// 2.2 左指针已经移动完毕，那么此时就相当于循环刚开始，同理直接移动右指针
if (need[r] == 0) {
right++;
continue;
}
//当且仅当已有字符串目标字符出现的次数小于目标字符串字符的出现次数时，count才会+1
//是为了后续能直接判断已有字符串是否已经包含了目标字符串的所有字符，不需要挨个比对字符出现的次数
if (have[r] < need[r]) {
count++;
}
//已有字符串中目标字符出现的次数+1
have[r]++;
//移动右指针
right++;
//当且仅当已有字符串已经包含了所有目标字符串的字符，且出现频次一定大于或等于指定频次
while (count == t.length()) {
//挡窗口的长度比已有的最短值小时，更改最小值，并记录起始位置
if (right - left < min) {
min = right - left;
start = left;
}
char l = s.charAt(left);
//如果左边即将要去掉的字符不被目标字符串需要，那么不需要多余判断，直接可以移动左指针
if (need[l] == 0) {
left++;
continue;
}
//如果左边即将要去掉的字符被目标字符串需要，且出现的频次正好等于指定频次，那么如果去掉了这个字符，
//就不满足覆盖子串的条件，此时要破坏循环条件跳出循环，即控制目标字符串指定字符的出现总频次(count）-1
if (have[l] == need[l]) {
count--;
}
//已有字符串中目标字符出现的次数-1
have[l]--;
//移动左指针
left++;
}
}
//如果最小长度还为初始值，说明没有符合条件的子串
if (min == s.length() + 1) {
return "";
}
//返回的为以记录的起始位置为起点，记录的最短长度为距离的指定字符串中截取的子串
return s.substring(start, start + min);
}
}复杂度分析 令 n 为数组长度。
|
class Solution:
def minWindow(self, s: str, t: str) -> str:
'''
sliding window
'''
target = Counter(t)
if len(s) < len(t) or len(set(s)) < len(set(t)) or set(s).intersection(set(t)) != set(t):
return ''
l = r = 0
tmp = {}
res = ''
required_count = len(t)
while r < len(s):
if s[r] in target:
tmp[s[r]] = tmp.get(s[r], 0) + 1
if tmp[s[r]] <= target[s[r]]:
required_count -= 1
while required_count == 0:
if s[l] in tmp:
if len(res) == 0 or len(s[l:r+1]) < len(res):
res = s[l:r+1]
tmp[s[l]] -= 1
if tmp[s[l]] < target[s[l]]:
required_count += 1
if tmp[s[l]] == 0:
tmp.pop(s[l])
l += 1
r += 1
return res |
//T:O(n)
class Solution {
public String minWindow(String s, String t) {
int[] count = new int[256];
for (char c : t.toCharArray()) {
count[c]++;
}
int len = t.length();
int min = Integer.MAX_VALUE;
int from = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
if (count[s.charAt(i)]-- > 0) {
len--;
}
while (len == 0) {
if (i - j + 1 < min) {
min = i - j + 1;
from = j;
}
if (++count[s.charAt(j++)] > 0) {
len++;
}
}
}
return (min == Integer.MAX_VALUE) ? "" : s.substring(from, from + min);
}
} |
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t) > len(s):
return ""
def is_insde(s, t):
for i in t.keys():
if (i not in s) or (s[i] < t[i]):
return False
return True
t_dict = Counter(t)
w_dict = Counter(s[0:len(t)])
res = ""
if is_insde(w_dict, t_dict):
res = s[0:len(t)]
left = 0
right = len(t)
while right < len(s):
while not is_insde(w_dict, t_dict) and right < len(s):
if s[right] not in w_dict:
w_dict[s[right]] = 1
else:
w_dict[s[right]] += 1
right += 1
while is_insde(w_dict, t_dict) and left < right:
if len(res) == 0:
res = s[left:right]
elif len(res) > (right - left):
res = s[left:right]
if w_dict[s[left]] > 1:
w_dict[s[left]] -= 1
else:
del w_dict[s[left]]
left += 1
return res
Time: O(N) Space: O( |
思路
代码//模版直接套用
class Solution {
public String minWindow(String s, String t) {
int left = 0;
int[] res = {0, Integer.MAX_VALUE};
HashMap<Character, Integer> map = new HashMap<>();
HashMap<Character, Integer> source = new HashMap<>();
for(int i = 0;i < t.length();i++){
char cur = t.charAt(i);
source.putIfAbsent(cur, 0);
source.put(cur, source.get(cur)+1);
}
for(int i = 0;i < s.length();i++){
char cur = s.charAt(i);
map.putIfAbsent(cur, 0);
map.put(cur, map.get(cur)+1);
while(included(map, source)){
if(i - left < res[1] - res[0]){
res[0] = left;
res[1] = i;
}
char leftChar = s.charAt(left);
left++;
map.put(leftChar, map.get(leftChar)-1);
}
}
return res[1] == Integer.MAX_VALUE?"":s.substring(res[0], res[1]+1);
}
public boolean included(HashMap<Character, Integer> map, HashMap<Character, Integer> source){
for(char key: source.keySet()){
if(!map.containsKey(key) || map.get(key) < source.get(key)){
return false;
}
}
return true;
}
}
//优化比较map
class Solution {
public String minWindow(String s, String t) {
int left = 0, budget = 0;
int[] res = {0, Integer.MAX_VALUE};
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0;i < t.length();i++){
char cur = t.charAt(i);
map.putIfAbsent(cur, 0);
map.put(cur, map.get(cur)+1);
budget++;
}
for(int i = 0;i < s.length();i++){
char cur = s.charAt(i);
if(map.containsKey(cur)){
int latest = map.get(cur);
if(latest > 0) budget--;
map.put(cur, map.get(cur) - 1);
}
while(budget <= 0){
if(i - left < res[1] - res[0]){
res[0] = left;
res[1] = i;
}
char leftC = s.charAt(left);
if(map.containsKey(leftC)){
map.put(leftC, map.get(leftC) + 1);
if(map.get(leftC) > 0) budget++;
}
left++;
}
}
return res[1] == Integer.MAX_VALUE?"":s.substring(res[0], res[1]+1);
}
}复杂度//直接套用模版 //优化 |
link:https://leetcode.com/problems/minimum-window-substring/ 代码 Javascriptconst minimumWindowSubstring = function (string, substring) {
let answer = ""
let map = {}
substring.split("").forEach((character) => (map[character] = (map[character] || 0) + 1))
let count = Object.keys(map).length
let left = 0
let right = -1
while (right < string.length) {
if (count === 0) {
if (!answer || right - left + 1 < answer.length) {
answer = string.slice(left, right + 1)
}
if (map[string[left]] !== undefined) {
map[string[left]]++
}
if (map[string[left]] > 0) {
count++
}
left++
} else {
right++
if (map[string[right]] !== undefined) {
map[string[right]]--
}
if (map[string[right]] === 0) {
count--
}
}
}
return answer
} |
思路
Java Code public String minWindow(String s, String t) {
int m = s.length(), n = t.length();
if (m < n) {
return "";
}
Map<Character, Integer> countMap = new HashMap<>();
int neededCount = 0;
for (char c : t.toCharArray()) {
countMap.put(c, countMap.getOrDefault(c, 0) + 1);
neededCount++;
}
int l = 0, r = 0, minLength = Integer.MAX_VALUE;
String str = "";
while (r < m) {
while (neededCount != 0 && r < m) {
char c = s.charAt(r);
if (countMap.containsKey(c)) {
if (countMap.get(c) > 0) {
neededCount--;
}
countMap.put(c, countMap.get(c) - 1);
}
r++;
}
while (l < m && neededCount == 0) {
if (r - l < minLength) {
minLength = r- l;
str = s.substring(l, r);
}
char c = s.charAt(l);
if (countMap.containsKey(c)) {
countMap.put(c, countMap.get(c) + 1);
if (countMap.get(c) > 0) {
neededCount++;
}
}
l++;
}
}
return str;
}时间&空间
|
IntuitionSliding window problem Algorithm in python3Complexity Analysis
|
/*Time complexity: O(S + T)
Space complexity: O(S + T)
*/
var minWindow = function(s, t) {
let left = 0;
let map = new Map();
let count = t.length;
let minLen = Number.MAX_VALUE;
let res = "";
for (let ele of t) {
if (!map.has(ele)) {
map.set(ele , 1);
} else {
map.set(ele, map.get(ele) + 1);
}
}
for (let i = 0; i < s.length; i++) {
if (map.has(s[i])) {
if (map.get(s[i]) > 0) {
count--;
}
map.set(s[i], map.get(s[i]) - 1);
}
while (count === 0) {
if (minLen > (i - left + 1)) {
minLen = i - left + 1;
res = s.substr(left, minLen);
}
if (map.has(s[left])) {
map.set(s[left], map.get(s[left]) + 1);
if (map.get(s[left]) > 0) {
count++;
}
}
left++;
}
}
return res;
}; |
|
思路非固定长度滑动窗口。首先右指针遍历数组。如果左右指针内的窗口包含目标字符串，那么右指针暂停前进，此时如果窗口长度小于之前的最小长度，那么更新最小长度和左右指针位置，并收缩左指针，直到窗口内不包含字符串为止。然后再移动右指针。 代码class Solution {
public String minWindow(String s, String t) {
int m = s.length();
int n = t.length();
if (m < n) {
return "";
}
int[] charsInT = new int[52]; // SC O(1)
countChars(t, 0, n-1, charsInT, false); // O(n)
int[] charsWindow = new int[52];
countChars(s, 0, n-2, charsWindow, false); // O(n)
int ansStart = -1;
int ansEnd = -1;
int minLen = Integer.MAX_VALUE;
int left = 0;
for (int right = n-1; right < m; right++) { // O(m)
countChars(s, right, right, charsWindow, false); // O(1)
while( exists(charsInT, charsWindow) ) { // O(1)
if (minLen > right - left + 1) {
minLen = right - left + 1;
ansStart = left;
ansEnd = right;
}
// move forward the left boundry
countChars(s, left, left, charsWindow, true); // O(1)
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(ansStart, ansEnd + 1);
}
private void countChars(String str, int start, int end, int[] count, boolean decrease) {
for (int i=start; i<=end; i++) {
char c = str.charAt(i);
if (Character.isLowerCase(c)) {
count[c - 'a'] += decrease ? -1 : 1;
} else if (Character.isUpperCase(c)) {
count[c - 'A' + 26] += decrease ? -1 : 1;
}
}
}
private boolean exists(int[] lookupChars, int[] windowChars) {
for (int i=0; i<lookupChars.length; i++) {
if (windowChars[i] < lookupChars[i]) {
return false;
}
}
return true;
}
}TC: O(m + n) |
思路滑动窗口 代码func minWindow(s string, t string) string {
minl:=0
minr:= len(s)
l, r := 0, 0
count:=0
memo := make([]int, 124)
for i := range t {
memo[t[i]]++
count++
}
for r < len(s) {
if memo[s[r]]>0 {
count--
}
memo[s[r]]--
for l<=r && count==0 {
if r-l<minr-minl {
minl,minr = l,r
}
if memo[s[l]]>=0 {
count++
}
memo[s[l]]++
l++
}
r++
}
if minr!=len(s) {
return s[minl:minr+1]
}else {
return ""
}
}复杂度分析
|
思路官方题解 代码使用语言：Python3 class Solution:
def minWindow(self, s: str, t: str) -> str:
if not t or not s:
return ""
# Dictionary which keeps a count of all the unique characters in t.
dict_t = Counter(t)
# Number of unique characters in t, which need to be present in the desired window.
required = len(dict_t)
# left and right pointer
l, r = 0, 0
# formed is used to keep track of how many unique characters in t are present in the current window in its desired frequency.
# e.g. if t is "AABC" then the window must have two A's, one B and one C. Thus formed would be = 3 when all these conditions are met.
formed = 0
# Dictionary which keeps a count of all the unique characters in the current window.
window_counts = {}
# ans tuple of the form (window length, left, right)
ans = float("inf"), None, None
while r < len(s):
# Add one character from the right to the window
character = s[r]
window_counts[character] = window_counts.get(character, 0) + 1
# If the frequency of the current character added equals to the desired count in t then increment the formed count by 1.
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
# Try and contract the window till the point where it ceases to be 'desirable'.
while l <= r and formed == required:
character = s[l]
# Save the smallest window until now.
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
# The character at the position pointed by the `left` pointer is no longer a part of the window.
window_counts[character] -= 1
if character in dict_t and window_counts[character] < dict_t[character]:
formed -= 1
# Move the left pointer ahead, this would help to look for a new window.
l += 1
# Keep expanding the window once we are done contracting.
r += 1
return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]复杂度分析 |
Idea:Sliding window. Increase right side till the substring has all chars in the string t, then increase left side until one char of the string t has fewer frequency than it should be in current substring. Codefrom collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
t_count = Counter(t)
desired = len(t_count)
k = 0
s_count = Counter()
length, start, end = math.inf, 0, 0
i = 0
for j in range(len(s)):
if s[j] in t_count:
s_count[s[j]] = s_count.get(s[j], 0) + 1
if s_count[s[j]] == t_count[s[j]]:
k += 1
while desired == k:
if j - i + 1 < length:
length = j - i + 1
start, end = i, j
if s[i] in s_count:
if s_count[s[i]] == t_count[s[i]]:
k -= 1
s_count[s[i]] -= 1
i += 1
return s[start:end+1] if length != math.inf else ""Compelxity:Time: O(N + M). N: the length of string s. M: the length of string t. We scan though string t to get the frequency of the chars. The scan twice of string s in worst case, once for the left side, once for the right side. |
|
思路: 复杂度分析:
代码(C++): class Solution {
public:
string minWindow(string s, string t) {
if (s.length() < t.length()) return "";
vector<int> freq(128, 0);
for (auto c : t)
freq[c]++;
int l = 0, minLeft = -1, cnt = 0, res = s.length() + 1;
for (int i = 0; i < s.length(); i++) {
freq[s[i]]--;
if (freq[s[i]] >= 0) cnt++;
while (cnt == t.length()) {
if (res > i - l + 1) {
res = i - l + 1;
minLeft = l;
}
freq[s[l]]++;
if (freq[s[l]] > 0) cnt--;
l++;
}
}
return (minLeft == -1) ? "" : s.substr(minLeft, res);
}
}; |
思路滑动窗口 代码class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null
|| s.length() == 0 || t.length() == 0
|| s.length() < t.length()) {
return "";
}
int[] map = new int[256];
int cnt = 0;
for (char c : t.toCharArray()) {
map[c]++;
if (map[c] == 1) {
cnt++;
}
}
char[] src = s.toCharArray();
int start = 0, end = 0;
int rStart = 0, rEnd = src.length;
for (end = 0; end < src.length; end++) {
map[src[end]]--;
if (map[src[end]] == 0) {
cnt--;
}
if (cnt == 0) {
while (map[src[start]]++ < 0) {
start++;
}
if (end - start < rEnd - rStart) {
rStart = start;
rEnd = end;
}
start++;
cnt++;
}
}
return rEnd == src.length ? "" : s.substring(rStart, rEnd + 1);
}
}复杂度
|
class Solution(object):
def minWindow(self, s, t):
l = r = 0
target = Counter(t)
target_cnt = len(target.keys())
res = ''
while r < len(s):
if s[r] in target:
target[s[r]] -= 1
if target[s[r]] == 0:
target_cnt -= 1
while target_cnt == 0 and l <= r:
if len(res) == 0 or len(s[l:r+1]) < len(res):
res = s[l:r+1]
if s[l] in target:
target[s[l]] += 1
if target[s[l]] > 0:
target_cnt += 1
l += 1
r += 1
return res T: n |
thoughts滑动窗口 + hashmap 这里需要两个hashmap 一个存需要的char的数目，一个存window里面的char的数目 还需要一个变量计数， 和needed的长度比较，是不是已经满足了， 这个变量只有当window里面的char对应的count和needed里面对应的count一样的时候才会+1或者减一 codefrom collections import defaultdict
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t or len(t) > len(s):
return ""
needed_map, window_map = defaultdict(int), defaultdict(int)
left = valid_count = 0
min_left = min_right = -1
for char in t:
needed_map[char] += 1
for i, char in enumerate(s):
if char in needed_map:
window_map[char] += 1
if window_map[char] == needed_map[char]:
valid_count += 1
while valid_count == len(needed_map):
if min_left == -1 or i - left + 1 <= min_right - min_left:
min_left, min_right = left, i+1
if s[left] in needed_map:
if window_map[s[left]] == needed_map[s[left]]:
valid_count -= 1
window_map[s[left]] -= 1
left += 1
return s[min_left:min_right]Complexitym == s.length, n == t.length 时间复杂度 O(m+n) 空间复杂度 O(n) |
public String minWindow(String s, String t) {
int[] count = new int[128];
int unique = 0;
for (char c : t.toCharArray()) {
if (count[c]++ == 0) unique++;
}
int start = -1;
int len = Integer.MAX_VALUE;
for (int l = 0, r = 0; r < s.length(); r++) {
if (count[s.charAt(r)]-- == 1) unique--;
while (unique == 0) {
if (r - l + 1 < len) {
start = l;
len = r - l + 1;
}
if (count[s.charAt(l++)]++ == 0) unique++;
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}Time: O(n) |
76. Minimum Window SubstringIntuition
Code/**
* @param {string} s
* @param {string} t
* @return {string}
*/
const minWindow = function(s, t) {
const targetFreq = getCharFreq(t);
const windowFreq = {};
let matches = 0; // match count of target chars within current window
let start = 0;
let minStart = 0;
let minWidth = Infinity;
for (let i = 0; i < s.length; i++) {
windowFreq[s[i]] = (windowFreq[s[i]] || 0) + 1;
if (windowFreq[s[i]] <= (targetFreq[s[i]] || 0)) {
matches += 1;
}
if (matches === t.length) {
while (windowFreq[s[start]] > (targetFreq[s[start]] || 0)) {
windowFreq[s[start++]] -= 1;
}
if (minWidth > i - start + 1) {
minWidth = i - start + 1;
minStart = start;
}
}
}
return minWidth === Infinity ? '' : s.substr(minStart, minWidth);
};
function getCharFreq(str) {
const charFreq = {};
for (const char of str) {
charFreq[char] = (charFreq[char] || 0) + 1;
}
return charFreq;
}Complexity Analysis
|
思路使用滑动窗口模板方法, 每次先向右移动窗口, 直到能够符合要求向左收缩窗口直到不符合要求, 并在其中更新状态信息 所以先右移窗口知道所有 t 中的字符都在窗口内, 直到 符合要求 然后持续左移窗口, 并且每次更新, 直到不符合要求 class Solution:
def minWindow(self, s: str, t: str) -> str:
left, right = 0, 0
valid = 0
count_dict = {key:0 for key in t}
target_dict = {}
for char in t:
target_dict[char] = target_dict.get(char, 0) + 1
min_left, min_length = 0, 1e9
while right < len(s):
c = s[right]
if c in count_dict:
count_dict[c] += 1
if count_dict[c] == target_dict[c]:
valid += 1
right += 1
while valid == len(target_dict):
if right - left < min_length:
min_length = right - left
min_left = left
c1 = s[left]
if c1 in count_dict:
count_dict[c1] -= 1
if count_dict[c1] < target_dict[c1]:
valid -= 1
left += 1
if min_length == 1e9:
return ""
else:
return s[min_left: min_left + min_length]复杂度n 为 s 的长度, m 为 t 的长度 时间复杂度: O(n+m) 因为两个指针每个 s 中字符最多访问一次, t 是 count 的时候遍历了一次 空间复杂度: O(m) count 的结果存储的空间复杂度是 O(m) |
|
思路： func minWindow(s string, t string) string {
have := [58]int{}
want := [58]int{}
count := 0
cur := 0
out := ""
if len(s) < len(t){
return out
}
for _,x := range t{
if want[x-'A'] == 0{
count++
}
want[x-'A']++
}
l,r := 0,-1
for l < len(s){
if r <len(s)-1&&cur != count{
r++
have[s[r]-'A']++
if want[s[r]-'A'] == have[s[r]-'A']{
cur++
}
}else{
have[s[l]-'A']--
if have[s[l]-'A'] < want[s[l]-'A']{
cur--
}
l++
}
if cur == count{
if out == "" || len(out) > r-l+1{
out = s[l:r+1]
}
}
}
return out
}时间复杂度：O（m+n） |
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import defaultdict
words = defaultdict(int)
for i in t:
words[i] += 1
#初始化
left = 0
right = 0
ns = len(s)
nt = len(t)
n = 0
result = ''
#保证起始位置有效
while right < ns and words[s[right]] == 0:
left += 1
right += 1
while right < ns:
#仅当left和right位置都是有效字符时才进行判断
if s[right] in t:
words[s[right]] -= 1
if words[s[right]] >= 0:
n += 1 #用于统计是否已满足条件
#缩小窗口，去除左端冗余
while words[s[left]] < 0:
words[s[left]] += 1
left += 1
#保证left处于有效字符位
while s[left] not in t:
left += 1
if n == nt and (result == '' or len(result) > right - left + 1):
result = s[left:right + 1]
right += 1
return result |
|
class Solution { } |
|
class Solution: |
|
思路： 代码： class Solution{ } 复杂度分析： |
思路关键点
代码
C++ Code: class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> umt;
unordered_map<char, int> ums;
for (auto& v : t) {
umt[v]++;
}
int left = 0, right = 0;
int count = 0;
int len = INT_MAX;
string res;
for (; right < s.length(); ++right) {
++ums[s[right]];
if (ums[s[right]] <= umt[s[right]]) {
++count;
}
while (count == t.length()) {
if (right - left + 1 < len) {
len = right - left + 1;
res = s.substr(left, len);
}
if (ums[s[left]] == umt[s[left]]) {
--count;
}
--ums[s[left]];
++left;
}
}
return res;
}
};
复杂度分析令 n 为数组长度。
|
76. 最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 示例 1： 输入：s = "ADOBECODEBANC", t = "ABC" 输入：s = "a", t = "a" 输入: s = "a", t = "aa" 提示： 1 <= s.length, t.length <= 105 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ 思路一用滑动窗口做 思路来自leetcode题解区 作者：Mcdull0921 用一个字典need来表示当前滑动窗口中需要的各元素的数量，一开始滑动窗口为空，用T中各元素来初始化这个need，当滑动窗口扩展或者收缩的时候，去维护这个need字典，例如当滑动窗口包含某个元素，我们就让need中这个元素的数量减1，代表所需元素减少了1个；当滑动窗口移除某个元素，就让need中这个元素的数量加1。 优化 代码class Solution {
public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0){
return "";
}
int[] need = new int[128];
//记录需要的字符的个数
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
//l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index
int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
//遍历所有字符
while (r < s.length()) {
char c = s.charAt(r);
if (need[c] > 0) {//需要字符c
count--;
}
need[c]--;//把右边的字符加入窗口
if (count == 0) {//窗口中已经包含所有字符
while (l < r && need[s.charAt(l)] < 0) {
need[s.charAt(l)]++;//释放右边移动出窗口的字符
l++;//指针右移
}
if (r - l + 1 < size) {//不能右移时候挑战最小窗口大小，更新最小窗口开始的start
size = r - l + 1;
start = l;//记录下最小值时候的开始位置，最后返回覆盖串时候会用到
}
//l向右移动后窗口肯定不能满足了 重新开始循环
need[s.charAt(l)]++;
l++;
count++;
}
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
} |
代码/**
* @param {string} s
* @param {string} t
* @return {string}
*/
const minWindow = (s, t) => {
let minLen = s.length + 1;
let start = s.length;
let map = {};
let missingType = 0;
for (const c of t) {
if (!map[c]) {
missingType++;
map[c] = 1;
} else {
map[c]++;
}
}
let l = 0, r = 0;
for (; r < s.length; r++) {
let rightChar = s[r];
if (map[rightChar] !== undefined) map[rightChar]--;
if (map[rightChar] == 0) missingType--;
while (missingType == 0) {
if (r - l + 1 < minLen) {
minLen = r - l + 1;
start = l;
}
let leftChar = s[l];
if (map[leftChar] !== undefined) map[leftChar]++;
if (map[leftChar] > 0) missingType++;
l++;
}
}
if (start == s.length) return "";
return s.substring(start, start + minLen);
};
|
思路sliding window + vector
Code// for debug
ostream& operator << (ostream &o, vector<int> a){
o << "[ ";
for(auto & x : a){
o << x << " ";
}
o << "]";
return o;
}
class Solution {
private:
int index(char & c){
// lower case
if( c >= 'a' && c <= 'z'){
return (c - 'a');
}
// upper case
else{
return (c - 'A' + 26);
}
}
// whether vs contains vt
bool contain(vector<int> &vs, vector<int> &vt){
const int n = vs.size();
for(int i = 0; i < n; ++i){
if(vs[i] < vt[i])
return false;
}
return true;
}
public:
string minWindow(string s, string t) {
const int n = t.length();
const int m = s.length();
if(n > m)
return "";
vector<int> vs(52), vt(52);
int ans_len = m+1;
string ans;
for(char & c : t){
vt[index(c)]++;
}
int j = 0;
for(int i = 0; i < m; ++i){
while(!contain(vs, vt)){
if(j >= m)
return ans;
vs[index(s[j++])]++;
}
int len = j - i;
if(ans_len > len){
ans_len = len;
ans = s.substr(i, len);
}
vs[index(s[i])]--;
}
return ans;
}
};Complexity Analysis: |
|
思路 |
思路滑动窗口
语言java 代码public String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0){
return "";
}
int[] need = new int[128];
//记录需要的字符的个数
for (int i = 0; i < t.length(); i++) {
need[t.charAt(i)]++;
}
//l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index
int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
//遍历所有字符
while (r < s.length()) {
char c = s.charAt(r);
if (need[c] > 0) {//需要字符c
count--;
}
need[c]--;//把右边的字符加入窗口
if (count == 0) {//窗口中已经包含所有字符
while (l < r && need[s.charAt(l)] < 0) {
need[s.charAt(l)]++;//释放右边移动出窗口的字符
l++;//指针右移
}
if (r - l + 1 < size) {//不能右移时候挑战最小窗口大小，更新最小窗口开始的start
size = r - l + 1;
start = l;//记录下最小值时候的开始位置，最后返回覆盖串时候会用到
}
//l向右移动后窗口肯定不能满足了 重新开始循环
need[s.charAt(l)]++;
l++;
count++;
}
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}复杂度分析
|
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
int start = 0, len = INT_MAX;
while (right < s.size()) {
char c = s[right];
right++;
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
while (valid == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return len == INT_MAX ?
"" : s.substr(start, len);
} |
思路滑动窗口 Python3代码class Solution:
def minWindow(self, s: str, t: str) -> str:
m=len(s)
n=len(t)
right=0
left=0
res="!"+s
d=defaultdict(int)
for i in t:
d[i]+=1
while right<m:
lt=s[right]
right+=1
if d[lt]>0:
n-=1
d[lt]-=1
if n==0:
while left<right and d[s[left]]!=0:
d[s[left]]+=1
left+=1
if right-left<len(res):
res=s[left:right]
n+=1
d[s[left]]+=1
left+=1
if res[0]=="!":
return ""
return res |
|
public String minWindow(String s, String t) { |
思路与昨天的题思路类似，只是把固定滑窗换成左右指针并用一个变量存储匹配的个数，为零时update最小结果 代码复杂度时间：o(n) |
【Day 46】76. 最小覆盖子串思路Copy 代码class Solution:
def minWindow(self, s: str, t: str) -> str:
mem = defaultdict(int)
for char in t:
mem[char]+=1
t_len = len(t)
minLeft, minRight = 0,len(s)
left = 0
for right,char in enumerate(s):
if mem[char]>0:
t_len-=1
mem[char]-=1
if t_len==0:
while mem[s[left]]<0:
mem[s[left]]+=1
left+=1
if right-left<minRight-minLeft:
minLeft,minRight = left,right
mem[s[left]]+=1
t_len+=1
left+=1
return '' if minRight==len(s) else s[minLeft:minRight+1]复杂度时间复杂度：O(N) 空间复杂度：O(N) |
最小覆盖字串思路官方 代码class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import defaultdict
words = defaultdict(int)
for i in t:
words[i] += 1
#初始化
left = 0
right = 0
ns = len(s)
nt = len(t)
n = 0
result = ''
#保证起始位置有效
while right < ns and words[s[right]] == 0:
left += 1
right += 1
while right < ns:
#仅当left和right位置都是有效字符时才进行判断
if s[right] in t:
words[s[right]] -= 1
if words[s[right]] >= 0:
n += 1 #用于统计是否已满足条件
#缩小窗口，去除左端冗余
while words[s[left]] < 0:
words[s[left]] += 1
left += 1
#保证left处于有效字符位
while s[left] not in t:
left += 1
if n == nt and (result == '' or len(result) > right - left + 1):
result = s[left:right + 1]
right += 1
return result复杂度分析
|
思路哈希表+ 双指针 代码class Solution:
def minWindow(self, s: str, t: str) -> str:
lns = len(s)
lnt = len(t)
if lnt > lns:
return ''
ret = ''
left = 0
dic = Counter(t)
for right, i in enumerate(s):
if i in dic:
dic[i] -= 1
if dic[i] >= 0:
lnt -= 1
while lnt == 0:
tmp = s[left]
left += 1
if tmp in dic:
dic[tmp] += 1
if dic[tmp] > 0:
lnt += 1
if not ret or len(ret) > right - left + 2:
ret = s[left - 1:right + 1]
return ret复杂度
|
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
let need = new Map(), count = t.length, newS = s.split(''), newT = t.split(''), start = 0;
newT.forEach(item => {
need.set(item, 1);
});
let i = 0, j = 0, min = Infinity;
while(j < s.length) {
if(newT.includes(newS[j])) {
let temp = need.get(newS[j]);
if(temp > 0) count -= 1
need.set(newS[j], temp - 1);
}
if(count === 0) {
while(i < j) {
let temp = need.get(newS[i]);
console.log(i)
if(temp < 0 || temp === undefined) {
if (temp !== undefined) need.set(newS[i], temp + 1)
i++
} else {
break
}
}
let len = j - i + 1;
if(len < min) {
min = len;
start = i
}
need.set(newS[i], need.get(newS[i]) + 1)
i++;
count++;
}
j++
}
return min === Infinity ? '' : s.substring(start, start + min)
}; |
|
代码 |
} |
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
let left = 0;
let right = 0;
// map集合存储t字符串里面需要的字符与需要的个数
const map = new Map();
for (let str of t) {
// 有该字符，则在该字符数上加一 没有则为1
map.set(str, map.has(str) ? map.get(str) + 1 : 1);
}
let minStr = '';
let stype = map.size;
while (right < s.length) {
const str = s[right];
// 如果当前字符在map中存在，则当前字符的需求数减一
if (map.has(str)) {
map.set(str, map.get(str) - 1);
// 如果这个字符的数量为0，则字符的类型减一
if(map.get(str)===0) stype--;
}
// 字符的类型为0，则当前子串全都满足要求
while (stype === 0) {
// 记录当前满足要求的字符串，和旧字符串进行比较，如果长度更小则更新最小子串
let newStr = s.substring(left,right+1);
// 因为 minStr是空串，肯定没有比空串小的，所以只要找到了满足要求的子串，就将最小的满足要求的字符串更新
if(!minStr || minStr.length>newStr.length) minStr = newStr;
const leftStr = s[left];
if(map.has(leftStr)) {
map.set(leftStr,map.get(leftStr)+1);
if(map.get(leftStr)===1)
stype++;
}
// 左指针右移一位
left++;
}
// 右指针右移一位
right++;
}
return minStr;
}; |
思路滑动窗口+双指针 代码class Solution {
private:
bool fn(unordered_map<char,int>a,unordered_map<char,int>b){
for(auto x:b)
{
if(a[x.first]<x.second)
return false;
}
return true;
}
public:
string minWindow(string s, string t) {
int windowSize=t.size(),len=s.size();
if(t.size()>len)
return "";
unordered_map<char,int>a,b;
for(char c:t)
b[c]++;
int l=0,r=0,ansL=-1,ansLen=100001;
while(r<len)
{
while(r<len&&!fn(a,b)){
if(r==len)
break;
a[s[r]]++;
r++;
}
while(fn(a,b)){
a[s[l]]--;
l++;
}
if(r-l+1<ansLen){
ansL=l-1;
ansLen=r-l+1;
}
}
if (ansL == -1 || ansLen == 100001)
return "";
return s.substr(ansL, ansLen);
}
};
复杂度分析
|
代码/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
let ans = ''
// 需要满足条件的字符串
let need = new Map()
for (let i in t) {
let a = t.charAt(i)
need.set(a, need.has(a) ? need.get(a) - 1 : -1)
}
let left = 0
let right = 0
// 需要匹配的字符数
let needMatch = t.length
while (right < s.length) {
// 即将进入窗口的字符
let c = s.charAt(right)
// 更新窗口内容
if (need.has(c)) {
need.set(c, need.get(c) + 1)
//匹配上一个字符,或者某个重复字符中的其中一个
if (need.get(c) <= 0) {
needMatch--
}
}
while (needMatch === 0 && right - left + 1 >= t.length) {
let newAns = s.slice(left, right + 1)
if (!ans || ans.length > newAns.length) {
ans = newAns
}
// 即将移出窗口的字符
let d = s.charAt(left)
if (need.has(d)) {
need.set(d, need.get(d) - 1)
// 如果字符移出后,该字符成为缺失字符, 需要再次匹配
if (need.get(d) < 0) {
needMatch++
}
}
left++
}
right++
}
return ans
}; |
|
class Solution(object):
def minWindow(self, s, t):
l = r = 0
target = Counter(t)
target_cnt = len(target.keys())
res = ''
while r < len(s):
if s[r] in target:
target[s[r]] -= 1
if target[s[r]] == 0:
target_cnt -= 1
while target_cnt == 0 and l <= r:
if len(res) == 0 or len(s[l:r+1]) < len(res):
res = s[l:r+1]
if s[l] in target:
target[s[l]] += 1
if target[s[l]] > 0:
target_cnt += 1
l += 1
r += 1
return res |
补作业这道题使用滑动窗口。用哈希表记录所有想要的字母出现次数为正数，其余的为0。cnt为t长度。开始遍历s时，一旦碰到想要的字母，那么cnt-=1，对于所有遇到的字母，如果当前哈希表出现次数为正，-=1。一旦cnt == 0，意味着我们找到了包含所有想要字母的子串，那么便移动左指针直到 hashtable[left] == 0停。意味着当前字母为想要字母，那么我们便比较当前字串长度，并取最短的。注意每次want[left]+=1 因为会有 想要的字母出现多次的情况。这样做是为了让想要的字母能在while loop中得到want[left] == 0而不是 want[left] == -1。因为无论如何，只要最后每次want[left]+=1， 那么while loop 中 ，对于想要的字母 want[left] 总是 == 0 的， 因为 我们把多余的还了回去。而对于不想要的，那么永远是 小于0 的，因为他们一开始起始数为0，出现两次便为 -2， 就算当前轮 want[left]+=1, 下一次遇到当前不想要字母，want[left] 最多为-1。而对于想要的，起始数永远大于等于1， 出现两次便want[left] = -1， 当前轮want[left] += 1后，下一次遇到这个想要的字母，want[left] 就会是0！ class Solution:
def minWindow(self, s: str, t: str) -> str:
want = defaultdict(int)
cnt = 0
for char in t:
cnt+=1
want[char] += 1
ansI, ansJ = 0, float('inf')
left = 0
for right, char in enumerate(s):
if want[char] >0:
cnt -=1
# unwanted char will have want[char] < 0
want[char]-=1
if cnt == 0:
while True:
c = s[left]
if want[c] == 0:
break
# want[s[i]] += 1, this allows duplicated wanted char to be saved back to normal stage
# which means, a wanted char will never gets to negative values
# for a unwanted char, in while loop, want[c] will always be negative as want[s[i]]+= 1 is after the while loop
# as wanted char always starts with a positive want[c], want[s[i]] += 1 will allows While to perform normally
# on wanted value, also will not affect the unwanted, because they are always want[c] < 0 during check condition.
want[c]+=1
left+=1
if ansJ-ansI > right-left:
ansJ, ansI = right, left
# now update left pointer
want[c]+=1
left+=1
cnt+=1
if ansJ == float("inf"):
return ""
else:
return s[ansI:ansJ+1]时间 O(n) |
思路
假设左指针l和右指针r初始化指向 当窗口包含 关键点
代码(mark大佬的)
JavaScript Code: /**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
const map = {}
const tLen = t.length
// 统计t的字符个数
for (let i = 0; i < tLen; i++) {
const char = t[i];
map[char] = map[char] || 0
map[char]--
}
let len = Infinity
let match = 0
let resLeft = 0
let resRight = 0
let left = 0
let right = 0
while (right < s.length) {
const char = s[right]
// 当前窗口出现t中的字符时
if (char in map) {
map[char]++
// 有可能出现多个，只有跟t的个数相同才是匹配的部分
if (map[char] <= 0) {
match++
}
}
// 当相等时，说明当前窗口已经出现t的字符了
while (match === tLen) {
// 判断当时窗口是否小于上次窗口
if (right - left + 1 < len) {
len = right - left + 1
resLeft = left
resRight = right
}
// 此时需要滑动窗口了，将左指针出窗口
const ch = s[left]
if (ch in map) {
map[ch]--
// 小于说明当前窗口中该字符的个数不符合了
// 则不匹配计数要减一
if (map[ch] < 0) {
match--
}
}
// 移动左指针，收缩窗口
left++
}
// 扩大窗口
right++
}
// 有可能找不到，需要判断是否返回空字符串
return len === Infinity ? '' : s.substring(resLeft, resRight + 1);
}; |
|
class Solution: |
|
方法 实现语言: C++
class Solution {
public:
string minWindow(string s, string t) {
vector<int> trecord(265, 0);
vector<int> srecord(265, 0);
for(int i = 0;i < t.size();i++)
{
trecord[t[i]]++; //构造频次表
}
int left = 0;
int right = 0;
int count = 0; //记录最小数量
string ret;
int retindex = INT_MAX;
while(right < s.size())
{
int index = s[right];
srecord[index]++;
if(trecord[index] > 0 && srecord[index] <= trecord[index])
{
count++;
}
while(count == t.size())
{
if((right - left +1) < retindex)
{
retindex = right -left + 1;
ret = s.substr(left, retindex); //从left截取right-left+1的长度
}
int leftindex = s[left];
srecord[leftindex]--;
if(srecord[leftindex] < trecord[leftindex])
{
count--;
}
left++;
}
right++;
}
return ret;
}
};复杂度分析: |
|
class Solution: |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
76. 最小覆盖子串
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/minimum-window-substring
前置知识
题目描述
The text was updated successfully, but these errors were encountered: