113 lines
2.9 KiB
Markdown
113 lines
2.9 KiB
Markdown
# 最小覆盖子串
|
||
|
||
## 题目
|
||
|
||
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
|
||
|
||
|
||
|
||
注意：
|
||
|
||
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
|
||
如果 s 中存在这样的子串，我们保证它是唯一的答案。
|
||
|
||
|
||
示例 1：
|
||
|
||
输入：s = "ADOBECODEBANC", t = "ABC"
|
||
输出："BANC"
|
||
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
|
||
示例 2：
|
||
|
||
输入：s = "a", t = "a"
|
||
输出："a"
|
||
解释：整个字符串 s 是最小覆盖子串。
|
||
示例 3:
|
||
|
||
输入: s = "a", t = "aa"
|
||
输出: ""
|
||
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
|
||
因此没有符合条件的子字符串，返回空字符串。
|
||
|
||
|
||
提示：
|
||
|
||
m == s.length
|
||
n == t.length
|
||
1 <= m, n <= 105
|
||
s 和 t 由英文字母组成
|
||
|
||
## 思路
|
||
|
||
- 统计
|
||
- hashMap<Character, Integer>
|
||
- 滑动窗口
|
||
- 判定
|
||
- 满足
|
||
- 更新答案
|
||
- 左指针右移
|
||
- 不满足
|
||
- 右指针右移
|
||
|
||
## 代码
|
||
|
||
```java
|
||
class Solution {
|
||
public String minWindow(String s, String t) {
|
||
// Init
|
||
Map<Character, Integer> map_s = new HashMap<>();
|
||
Map<Character, Integer> map_t = new HashMap<>();
|
||
|
||
// Traverse: t
|
||
for (char ch : t.toCharArray()) {
|
||
map_t.put(ch, map_t.getOrDefault(ch, 0) + 1);
|
||
}
|
||
|
||
// Traverse: s [left, right]
|
||
int left = 0, right = 0;
|
||
int minLen = Integer.MAX_VALUE, minLeft = 0, minRight = 0;
|
||
int count = 0;
|
||
while (right < s.length()) {
|
||
char ch = s.charAt(right);
|
||
map_s.put(ch, map_s.getOrDefault(ch, 0) + 1);
|
||
if (map_t.containsKey(ch) && map_s.get(ch).equals(map_t.get(ch))) {
|
||
count++;
|
||
}
|
||
while (count == map_t.size()) {
|
||
if (right - left + 1 < minLen) {
|
||
minLen = right - left + 1;
|
||
minLeft = left;
|
||
minRight = right;
|
||
}
|
||
char leftCh = s.charAt(left);
|
||
map_s.put(leftCh, map_s.get(leftCh) - 1);
|
||
if (map_t.containsKey(leftCh) && map_s.get(leftCh) < map_t.get(leftCh)) {
|
||
count--;
|
||
}
|
||
left++;
|
||
}
|
||
right++;
|
||
}
|
||
|
||
if (minLen == Integer.MAX_VALUE) {
|
||
return "";
|
||
} else {
|
||
return s.substring(minLeft, minRight + 1);
|
||
}
|
||
|
||
}
|
||
}
|
||
```
|
||
|
||
## 坑点
|
||
|
||
```
|
||
<来自讨论区>
|
||
我想说的是 Java 用Map记录字母出现个数的写法，
|
||
最后一个测试用例通不过时，要明白一件事。
|
||
Integer是对象啊。。。
|
||
Integer会缓存频繁使用的数值，
|
||
数值范围为-128到127，在此范围内直接返回缓存值。
|
||
超过该范围就会new 一个对象。
|
||
浪费了我两个小时，希望有这种情况的老哥注意一下。
|
||
``` |