给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 java实现
时间: 2023-11-27 14:54:18 浏览: 36
可以使用滑动窗口算法来解决这个问题。具体步骤如下:
1. 定义两个指针 left 和 right,分别表示窗口的左右边界。
2. 移动右指针,扩大窗口,直到包含了所有 t 中的字符。
3. 移动左指针,缩小窗口,直到不再包含所有 t 中的字符。在移动左指针的过程中,记录最小子串的起始位置和长度。
4. 重复步骤2和3,直到右指针到达字符串 s 的末尾。
以下是 Java 代码实现:
```java
public String minWindow(String s, String t) {
int[] need = new int[128];
int[] window = new int[128];
for (char c : t.toCharArray()) {
need[c]++;
}
int left = 0, right = 0;
int count = 0;
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
char c1 = s.charAt(right);
if (need[c1] > 0) {
window[c1]++;
if (window[c1] <= need[c1]) {
count++;
}
}
right++;
while (count == t.length()) {
if (right - left < len) {
start = left;
len = right - left;
}
char c2 = s.charAt(left);
if (need[c2] > 0) {
window[c2]--;
if (window[c2] < need[c2]) {
count--;
}
}
left++;
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
```
其中,need 数组记录 t 中每个字符出现的次数,window 数组记录当前窗口中每个字符出现的次数。count 表示当前窗口中包含了多少 t 中的字符。start 和 len 分别记录最小子串的起始位置和长度。