给定两个字符串 source 和 target. 求 source 中最短的包含 target 中每一个字符的子串.
- 如果没有答案, 返回 "".
- 保证答案是唯一的.
- target 可能包含重复的字符, 而你的答案需要包含至少相同数量的该字符.
在线评测地址：领扣题库官网
样例 1:
输入: source = "abc", target = "ac"
输出: "abc"样例 2:
输入: source = "adobecodebanc", target = "abc"
输出: "banc"解释: "banc" 是 source 的包含 target 的每一个字符的最短的子串.
样例 3:
输入: source = "abc", target = "aa"
输出: ""解释: 没有子串包含两个 'a'.
解题思路
- 本题采用滑窗法，滑窗法是双指针技巧，指针left和right分别指向窗口两端，从左向右滑动，实施维护这个窗口。我们的目标是找到source中涵盖target全部字母的最小窗口，即为最小覆盖子串。
算法流程 -
变量定义：
- 哈希表counter_s和counter_t表示数组source和target中有效字符的出现次数，其中，我们将有效字符定义为target中出现的字符。
- start是最小覆盖子串的起始索引，minlen是最小覆盖子串的长度（从0计）。
- valid表示source的窗口中满足counter_t出现次数要求的字符的个数。注意，相同的字符只计算一次。
- left和right分别指向滑窗两端。
-
算法流程：
- 初始化：left指针和right指针都指向s[0]。
- 移动窗口右边界：将right指针右移，如果指向的字符ch是有效字符，那么counter_s[ch] += 1。如果字符ch的出现次数达标，那么valid += 1。
-
当我们得到一个可行窗口，即包含target的全部字母的窗口时:
- 判断此时的子串是否长度更小。如果是，更新子串的起始位置start和长度minlen。
- 移动窗口左边界：将left右移，如果离开的字符left_ch是有效字符，那么counter_s[left_ch] -= 1。如果字符left_ch的出现次数不再达标，那么valid -= 1。
- 如果窗口依然可行，循环步骤3。否则，跳转至步骤2。
复杂度分析：
- 时间复杂度：O(n)，n为字符串source的长度。
- 空间复杂度：O(n)。
代码
public class Solution {
/**
* @param source : A string
* @param target: A string
* @return: A string denote the minimum window, return "" if there is no such a string
*/
public String minWindow(String source , String target) {
// 初始化counter_s和counter_t
Map<Character, Integer> counter_t = new HashMap<Character, Integer>();
Map<Character, Integer> counter_s = new HashMap<Character, Integer>();
for (int i = 0; i < target.length(); i++) {
int count = counter_t.getOrDefault(target.charAt(i), 0);
counter_t.put(target.charAt(i), count + 1);
}
int left = 0, valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = -1, minlen = Integer.MAX_VALUE;
for (int right = 0; right < source.length(); right ++){
// 移动右边界, ch 是将移入窗口的字符
char ch = source.charAt(right);
if (counter_t.containsKey(ch)) {
counter_s.put(ch, counter_s.getOrDefault(ch, 0) + 1);
if (counter_s.get(ch).compareTo(counter_t.get(ch)) == 0) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while (valid == counter_t.size()) {
// 更新最小覆盖子串
if (right - left < minlen) {
start = left;
minlen = right - left;
}
// left_ch 是将移出窗口的字符
char left_ch = source.charAt(left);
// 左移窗口
left ++;
// 进行窗口内数据的一系列更新
if (counter_t.containsKey(left_ch)) {
if (counter_t.get(left_ch).equals(counter_s.get(left_ch))) {
valid--;
}
counter_s.put(left_ch, counter_s.getOrDefault(left_ch, 0) - 1);
}
}
}
// 返回最小覆盖子串
return start == -1 ? "" : source.substring(start, start + minlen + 1);
}
}更多题解参考：九章官网solution
