题目

image.png

思路

  • 第一步：根据条件先扩大窗口，直至满足条件为止，然后进行第二步。
  • 第二步，再收缩窗口，直至不满足条件为此，此时又回到第一步。
  • 最后根据条件终止

    代码

    1.   public String minWindow(String s, String t) {
    2.       int len = s.length(), count = t.length();
    3.       if (len < count) return "";
    4.       HashMap<Character, Integer> map = new HashMap<>();
    5.       for (int k = 0; k < count; k++) {
    6.           char ch = t.charAt(k);
    7.           map.put(ch, map.getOrDefault(ch, 0) + 1);
    8.       }
    9.       int l = -1, r = len;
    10.       //扩大窗口
    11.       for (int i = 0, j = 0; j < len; j++) {
    12.           char key = s.charAt(j);
    13.           if (map.containsKey(key)) {
    14.               int val = map.get(key);
    15.               map.put(key, val - 1);
    16.               if (val > 0) count--;
    17.           }
    18.           //收缩窗口
    19.           while (count == 0) {
    20.               if (r - l > j - i + 1) {
    21.                   r = j + 1;
    22.                   l = i;
    23.               }
    24.               char c = s.charAt(i);
    25.               if (map.containsKey(c)) {
    26.                   int val = map.get(c);
    27.                   map.put(c, val + 1);
    28.                   if (val >= 0) count++;
    29.               }
    30.               i++;
    31.           } 
    32.       }
    33.       return l == -1 ? "" : s.substring(l, r);
    34.   }
    最小覆盖子串