题目描述
给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
如果 s 中存在多个符合条件的子字符串，返回任意一个。
注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3：
输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 105s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode.cn/problems/minimum-window-substring/
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | class Solution:
def minWindow(self, s: str, t: str) -> str:
m, n = len(s), len(t)
if n > m:
return ""
need, window = defaultdict(int), defaultdict(int)
for c in t:
need[c] += 1
start, minLen = 0, inf
left, right = 0, 0
while right < m:
window[s[right]] += 1
right += 1
while self.check(need, window):
if right - left < minLen:
minLen = right - left
start = left
window[s[left]] -= 1
left += 1
return "" if minLen == inf else s[start : start + minLen]
def check(self, need, window):
for k, v in need.items():
if window[k] < v:
return False
return True
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
public String minWindow(String s, String t) {
int m = s.length(), n = t.length();
if (n > m) {
return "";
}
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char ch : t.toCharArray()) {
need.merge(ch, 1, Integer::sum);
}
int start = 0, minLen = Integer.MAX_VALUE;
int left = 0, right = 0;
while (right < m) {
window.merge(s.charAt(right++), 1, Integer::sum);
while (check(need, window)) {
if (right - left < minLen) {
minLen = right - left;
start = left;
}
window.merge(s.charAt(left++), -1, Integer::sum);
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
private boolean check(Map<Character, Integer> need, Map<Character, Integer> window) {
for (Map.Entry<Character, Integer> entry : need.entrySet()) {
if (window.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | func minWindow(s string, t string) string {
m, n := len(s), len(t)
if n > m {
return ""
}
need, window := make(map[byte]int), make(map[byte]int)
for _, r := range t {
need[byte(r)]++
}
start, minLen := 0, math.MaxInt32
left, right := 0, 0
for right < m {
window[s[right]]++
right++
for check(need, window) {
if right-left < minLen {
minLen = right - left
start = left
}
window[s[left]]--
left++
}
}
if minLen == math.MaxInt32 {
return ""
}
return s[start : start+minLen]
}
func check(need, window map[byte]int) bool {
for k, v := range need {
if window[k] < v {
return false
}
}
return true
}
|
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution:
def minWindow(self, s: str, t: str) -> str:
m, n = len(s), len(t)
if n > m:
return ""
need, window = defaultdict(int), defaultdict(int)
needCount, windowCount = 0, 0
for c in t:
if need[c] == 0:
needCount += 1
need[c] += 1
start, minLen = 0, inf
left, right = 0, 0
while right < m:
ch = s[right]
right += 1
if ch in need:
window[ch] += 1
if window[ch] == need[ch]:
windowCount += 1
while windowCount == needCount:
if right - left < minLen:
minLen = right - left
start = left
ch = s[left]
left += 1
if ch in need:
if window[ch] == need[ch]:
windowCount -= 1
window[ch] -= 1
return "" if minLen == inf else s[start : start + minLen]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | class Solution {
public String minWindow(String s, String t) {
int m = s.length(), n = t.length();
if (n > m) {
return "";
}
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
int needCount = 0, windowCount = 0;
for (char ch : t.toCharArray()) {
if (!need.containsKey(ch)) {
needCount++;
}
need.merge(ch, 1, Integer::sum);
}
int start = 0, minLen = Integer.MAX_VALUE;
int left = 0, right = 0;
while (right < m) {
char ch = s.charAt(right++);
if (need.containsKey(ch)) {
int val = window.getOrDefault(ch, 0) + 1;
if (val == need.get(ch)) {
windowCount++;
}
window.put(ch, val);
}
while (windowCount == needCount) {
if (right - left < minLen) {
minLen = right - left;
start = left;
}
ch = s.charAt(left++);
if (need.containsKey(ch)) {
int val = window.get(ch);
if (val == need.get(ch)) {
windowCount--;
}
window.put(ch, val - 1);
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | func minWindow(s string, t string) string {
m, n := len(s), len(t)
if n > m {
return ""
}
need, window := make(map[byte]int), make(map[byte]int)
needCount, windowCount := 0, 0
for _, r := range t {
if need[byte(r)] == 0 {
needCount++
}
need[byte(r)]++
}
start, minLen := 0, math.MaxInt32
left, right := 0, 0
for right < m {
ch := s[right]
right++
if v, ok := need[ch]; ok {
window[ch]++
if window[ch] == v {
windowCount++
}
}
for windowCount == needCount {
if right-left < minLen {
minLen = right - left
start = left
}
ch = s[left]
left++
if v, ok := need[ch]; ok {
if window[ch] == v {
windowCount--
}
window[ch]--
}
}
}
if minLen == math.MaxInt32 {
return ""
}
return s[start : start+minLen]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | class Solution {
func minWindow(_ s: String, _ t: String) -> String {
let m = s.count, n = t.count
if n > m {
return ""
}
var need = [Character: Int]()
var window = [Character: Int]()
for ch in t {
need[ch, default: 0] += 1
}
let sArray = Array(s)
var start = 0, minLen = Int.max
var left = 0, right = 0
while right < m {
let ch = sArray[right]
window[ch, default: 0] += 1
right += 1
while check(need, window) {
if right - left < minLen {
minLen = right - left
start = left
}
let leftChar = sArray[left]
window[leftChar, default: 0] -= 1
left += 1
}
}
return minLen == Int.max ? "" : String(sArray[start..<start + minLen])
}
private func check(_ need: [Character: Int], _ window: [Character: Int]) -> Bool {
for (key, value) in need {
if window[key, default: 0] < value {
return false
}
}
return true
}
}
|