给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串,则返回空字符串 `""` 。java
时间: 2023-10-24 07:08:30 浏览: 42
你可以使用滑动窗口算法来解决这个问题。首先,我们可以创建两个指针,left 和 right,分别指向子串的左边界和右边界。
然后,我们可以使用一个哈希表来记录字符串 t 中每个字符的出现次数。接下来,我们不断移动右指针,将字符添加到窗口中,并更新哈希表。当窗口中包含了 t 中的所有字符时,我们可以尝试移动左指针来缩小窗口的大小,以找到最小的子串。
具体的操作如下:
1. 初始化 left 和 right 指针为 0。
2. 初始化一个哈希表 need,用于记录字符串 t 中每个字符的出现次数。
3. 初始化一个哈希表 window,用于记录当前窗口中每个字符的出现次数。
4. 初始化 count 变量为 0,表示当前窗口中已经包含了 t 中的字符的个数。
5. 初始化 minLen 变量为一个比较大的数,用于记录最小子串的长度。
6. 初始化 start 变量为 0,用于记录最小子串的起始位置。
7. 循环遍历右指针 right,直到 right 指向字符串 s 的末尾:
- 将右指针所指向的字符加入到窗口中,并更新 window 和 count。
- 如果 window 中某个字符的出现次数等于 need 中该字符的出现次数,则说明已经找到了一个匹配的字符。
- 如果 count 等于 t 的长度,则说明当前窗口中已经包含了 t 中的所有字符。
- 此时,我们可以尝试移动左指针来缩小窗口的大小,以找到更小的子串。具体操作如下:
- 如果当前窗口的大小小于 minLen,则更新 minLen 和 start 的值。
- 将左指针所指向的字符移出窗口,并更新 window 和 count。
- 左指针右移一位。
8. 返回最小子串,即从字符串 s 中的第 start 个位置开始,长度为 minLen 的子串。
下面是使用 Java 实现滑动窗口算法的示例代码:
```java
import java.util.HashMap;
import java.util.Map;
public class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int count = 0;
int minLen = Integer.MAX_VALUE;
int start = 0;
while (right < s.length()) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
if (need.containsKey(c) && window.get(c).equals(need.get(c))) {
count++;
}
while (count == t.length()) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
char d = s.charAt(left);
if (need.containsKey(d) && window.get(d).equals(need.get(d))) {
count--;
}
window.put(d, window.get(d) - 1);
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
```