LeetCode (5) 最小覆盖子串

请注意，本文编写于 1035 天前，最后修改于 1035 天前，其中某些信息可能已经过时。

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

https://leetcode-cn.com/problems/minimum-window-substring/

方法

滑动窗口思想

在滑动窗口类型的问题中都会有两个指针。一个用于「延伸」现有窗口的 r 一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。在 s 上滑动窗口，移动指针 r 扩大窗口直到能容纳所有t的字符，停止扩张收缩 l 指针，如果能收缩就收缩直到 l 达到最小窗口。

解题思路

这里的难点主要在两个，如何实现窗口，另一个是如何判断划定的窗口里包含了所有的目标字符串。

我原本的第一种思路，做两次遍历第一次窗口遍历第二次窗口移动遍历，这种方式时间复杂度太高，直接就会超时也不符合题干的要求。

第二次看了题解思路，我知道了原来是右边扩张一下左边再收缩的方式移动窗口，就设计了切割字符串的格式，但是字符串频繁切割会导致性能问题，在执行大字符串操作出现了超时，大概要3秒，只能再换一种。

第三种，用哈希表来存储字符串和判断，最终时间确实快了相当多！

定义两个Map<字符，字符数量>，目标字符串和窗口中符合的字符串。

Map<Character, Integer> originMap = new HashMap<>(171);
Map<Character, Integer> windowsMap = new HashMap<>(171);

1.移动窗口的右边的节点，直到满足字符串在target里。这里有个隐藏条件，我们最后一个字符一定是在Target字符串里，所以我们在扫描的时候可以快速忽略掉不在Target里的字符串。
2.当满足字符串在target里，这时候移动左边节点，直到窗口里的字符串不满足target。同样有个隐藏条件，左边的字符一定是在Target里。
3.在满足条件的字符进入或者出去的时候要注意刷新windowsMap
4.我定义了一个Map用于存储所有满足的target的字符串，最后再过滤出最小的

完整代码

package org.chenly.study;

import java.util.HashMap;
import java.util.Map;
import java.util.function.BiFunction;

/**
 * https://leetcode-cn.com/problems/minimum-window-substring/
 *
 * @author chenly
 * @create 2020-11-20 22:01
 */
public class MinWindowSubstring76 {
   public static String minWindow(String s, String t) {
      if (s.length() < t.length()) {
         return "";
      }
      Map<Character, Integer> originMap = new HashMap<>(171);
      Map<Character, Integer> windowsMap = new HashMap<>(171);

      for (char c : t.toCharArray()) {
         originMap.compute(c, add());
      }

      Map<Integer, String> integerStringMap = new HashMap<>();

      int left = 0;
      int right = 0;
      String windows = "";
      while (right < s.length()) {
         char rightChar = s.charAt(right);
         //扫到满足的字符
         if (originMap.containsKey(rightChar)) {
            windowsMap.compute(rightChar, add());

            while (equal(windowsMap, originMap) && left <= right) {
                //将符合的字符串记录在一个新map里
               windows = s.substring(left, right + 1);
               integerStringMap.put(windows.length(), windows);

               char leftChar = s.charAt(left);
               //扫到满足的字符
               if (originMap.containsKey(leftChar)) {
                  windowsMap.compute(leftChar, sub());

               }
               left++;
            }

         }
         right++;

      }
      return integerStringMap.entrySet()
            .stream()
            .min(Map.Entry.comparingByKey())
            .map(Map.Entry::getValue)
            .orElse("");
   }

   private static BiFunction<Character, Integer, Integer> sub() {
      return (character, integer) -> {
         if (integer == null) {
            return 0;
         }
         return --integer;
      };
   }

   private static BiFunction<Character, Integer, Integer> add() {
      return (character, integer) -> {
         if (integer == null) {
            return 1;
         }
         return ++integer;
      };
   }

   private static boolean equal(Map<Character, Integer> windowsMap, Map<Character, Integer> originMap) {
      return originMap.entrySet()
            .stream()
            .allMatch(entry -> windowsMap.getOrDefault(entry.getKey(), 0) >= entry.getValue());

   }

   public static void main(String[] args) {

      System.out.println(minWindow(
            "ADOBECODEBANC",
            "ABC"));

   }
}

内存占用优化

用于存储结果的map很显然有点多余，所以想办法去掉它

public static String minWindow(String s, String t) {
   if (s.length() < t.length()) {
      return "";
   }
   Map<Character, Integer> originMap = new HashMap<>();
   Map<Character, Integer> windowsMap = new HashMap<>();

   for (char c : t.toCharArray()) {
      originMap.compute(c, add());
   }

   int left = 0;
   int right = 0;
   String windows = "";
   int min = Integer.MAX_VALUE;
   while (right < s.length()) {
      char rightChar = s.charAt(right);
      if (originMap.containsKey(rightChar)) {
         windowsMap.compute(rightChar, add());

         while (equal(windowsMap, originMap) && left <= right) {

            if (right - left + 1 < min) {
               windows = s.substring(left, right + 1);
               min = right - left + 1;
            }
            char leftChar = s.charAt(left);
            if (originMap.containsKey(leftChar)) {
               windowsMap.compute(leftChar, sub());

            }
            left++;
         }

      }
      right++;

   }
   return windows;
}

失败方法

 //复杂度不符合 超时
   /* public static String minWindow(String s, String t) {
         if(s.length()<t.length()){
            return "";
         }
         int windowsLength = t.length();
         while (windowsLength<=s.length()){
            String windows = "";
            int left = 0;
            int right = windowsLength;
            while (windows.length() <= s.length()) {

               windows = s.substring(left, right);
               if (equals(windows, t)) {
                  return windows;
               } else {
                  left = left + 1;
                  right = right + 1;
                  if (right > s.length()) {
                     break;
                  }
               }

            }
            windowsLength++;

         }

         return "";

      }*/

   //字符串过长 超时
   /*public static String minWindow1(String s, String t) {
      if (s.length() < t.length()) {
         return "";
      }
      Map<Integer, String> integerStringMap = new HashMap<>();

      String windows = "";

      int left = 0;
      int right = t.length();
      while (right <= s.length()) {
         windows = s.substring(left, right);
         if (equals(windows, t)) {
            left++;
            integerStringMap.put(windows.length(), windows);
         } else {
            right++;
         }
      }

      return integerStringMap.entrySet()
            .stream()
            .min(Map.Entry.comparingByKey())
            .map(Map.Entry::getValue)
            .orElse("");

   }

   private static boolean equals(String temp, String t) {
      char[] chars1 = t.toCharArray();
      int a = 0;
      for (char c : chars1) {
         if (temp.indexOf(c) != -1) {
            a++;
            temp = temp.substring(0, temp.indexOf(c)) + temp.substring(temp.indexOf(c) + 1);
         }
      }
      return a == t.length();
   }*/

LeetCode

LeetCode (5) 最小覆盖子串

题目

方法

解题思路

完整代码

内存占用优化

失败方法

添加新评论

评论列表

LeetCode (5) 最小覆盖子串

题目

方法

解题思路

完整代码

内存占用优化

失败方法

LeetCode (4) 二叉树的最小深度

设计模式(7)-装饰模式（Decorator Pattern）

添加新评论

评论列表