说个题外话，H-1B 最严政策出来后，湾区工程师还打算留美么？

给定两个字符串 source 和 target. 求 source 中最短的包含 target 中每一个字符的子串.

1. 如果没有答案, 返回 “”.
2. 保证答案是唯一的.
3. 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 分别指向滑窗两端。

• 算法流程：

  1. 初始化：left 指针和 right 指针都指向 s[0]。
  2. 移动窗口右边界：将 right 指针右移，如果指向的字符 ch 是有效字符，那么 counter_s[ch] += 1 。如果字符 ch 的出现次数达标，那么 valid += 1 。
  3. 当我们得到一个可行窗口，即包含 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);     } } 

大佬有話說 (0)