给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
- 示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
- 示例 2：
输入：s = “a”, t = “a”
输出：”a”
滑动窗口解法：
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
47
| object MinWindow {
def main(args: Array[String]): Unit = {
println(minWindow("ADABDVCODEBANC", "ABCC"))
println(minWindow("ADABDVCODEBANC", "ABCHH"))
}
def minWindow(s: String, t: String): String = {
if (s == null || (s.length == 0) || t == null || (t.length == 0)) return ""
val dict = new Array[Int](256)
var needCount = t.length
t.toCharArray.foreach(a => dict(a.toInt) += 1)
var start = 0
var end = 0
var minValue = Int.MaxValue
var min = (0, 0)
while (end < s.length) {
val c = s.charAt(end)
if (dict(c) > 0) {
needCount -= 1
}
dict(c) -= 1
if (needCount == 0) {
while (start < end && dict(s.charAt(start)) < 0) {
dict(s.charAt(start)) += 1
start += 1
}
if (minValue > (end - start + 1)) {
minValue = end - start + 1
min = (start, end)
}
dict(s.charAt(start)) += 1
start += 1
needCount += 1
}
end += 1
}
if (minValue == Int.MaxValue) "" else s.substring(min._1, min._2 + 1)
}
}
|