杂志社网站建设,萧山区网站建设,家居用品东莞网站建设,骏域网络科技有限公司优质博文#xff1a;IT-BLOG-CN 一、题目
给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串#xff0c;则返回空字符串 。 对于t中重复字符#xff0c;我们寻找的子字符串中该字符数量必须不少于t中该字符数量… 优质博文IT-BLOG-CN 一、题目
给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串则返回空字符串 。 对于t中重复字符我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 如果s中存在这样的子串我们保证它是唯一的答案。 示例 1 输入s ADOBECODEBANC, t ABC 输出BANC 解释最小覆盖子串 “BANC” 包含来自字符串t的A、B和C。
示例 2 输入s a, t a 输出a 解释整个字符串 s 是最小覆盖子串。
示例 3: 输入: s a, t aa 输出: “” 解释: t中两个字符a均应包含在s的子串中 因此没有符合条件的子字符串返回空字符串。 m s.length n t.length 1 m, n 105 s和t由英文字母组成 进阶 你能设计一个在o(mn)时间内解决此问题的算法吗
二、代码
思想 我们用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针一个用于「延伸」现有窗口的r指针和一个用于「收缩」窗口的l指针。在任意时刻只有一个指针运动而另一个保持静止。我们在s上滑动窗口通过移动r指针不断扩张窗口。当窗口包含t全部所需的字符后如果能收缩我们就收缩窗口直到得到最小窗口。
如何判断当前的窗口包含所有t所需的字符呢我们可以用一个哈希表表示t中所有的字符以及它们的个数用一个哈希表动态维护窗口中所有的字符以及它们的个数如果这个动态表中包含t的哈希表中的所有字符并且对应的个数都不小于t的哈希表中各个字符的个数那么当前的窗口是「可行」的。 注意这里t中可能出现重复的字符所以我们要记录字符的个数。 优化 如果sXX⋯XABCXXXXtABC那么显然[XX⋯XABC]是第一个得到的「可行」区间得到这个可行区间后我们按照「收缩」窗口的原则更新左边界得到最小区间。我们其实做了一些无用的操作就是更新右边界的时候「延伸」进了很多无用的X更新左边界的时候「收缩」扔掉了这些无用的X做了这么多无用的操作只是为了得到短短的ABC。没错其实在s中有的字符我们是不关心的我们只关心t中出现的字符我们可不可以先预处理s扔掉那些t中没有出现的字符然后再做滑动窗口呢也许你会说这样可能出现XXABXXC的情况在统计长度的时候可以扔掉前两个X但是不扔掉中间的X怎样解决这个问题呢优化后的时空复杂度又是多少这里代码给出没有优化的版本。
class Solution {// 1、通过 hashMap 记录 t 中的字符串和个数// 2、通过 fast slow 快慢指针记录最短字符串的位置// 3、通过 hashMap 记录当前符合要求的字符串和个数MapCharacter, Integer ori new HashMap();// 定义一个变量保存字串的大小并将符合要求的字串fast/slow指针赋值给resL,resRint fast 0, slow 0, len Integer.MAX_VALUE, resL -1, resR -1;MapCharacter, Integer cur new HashMap();public String minWindow(String s, String t) {// 4、将需要判断的字串维护在hashMap中for (int i 0; i t.length(); i) {ori.put(t.charAt(i), ori.getOrDefault(t.charAt(i),0) 1);}// 5、开始遍历s串通过快慢指针while (fast s.length() slow fast) {// 6、将s逐个维护在hashMap中cur.put(s.charAt(fast), cur.getOrDefault(s.charAt(fast), 0) 1);// 7、当新加入字符后需要判断是否满足最小字串请求并且小于之前字串的长度while (check(t.length())) {// left 还没有移动所以下面的判断不能放在 while循环中if ((fast - slow 1) len) {len fast - slow 1;resL slow;resR fast 1;}// 将cur中slow下标的串-1cur.put(s.charAt(slow), cur.getOrDefault(s.charAt(slow), 0) -1);slow;}// 循环退出条件fast;}return resL -1 ? : s.substring(resL, resR);}private boolean check(Integer len) {// 如果 fast 小于 t 的长度直接返回 falseif (fast len - 1) {return false;}// 遍历 ori 或者 curIterator iterator ori.entrySet().iterator();while (iterator.hasNext()) {// 如果 cur 包含该元素val ori.val 则表示成功否则失败Map.Entry entry (Map.Entry)iterator.next();Character key (Character)entry.getKey();Integer val (Integer)entry.getValue();// 当前返回的串的个数小于目标串t的个数说明不符合直接退出if (cur.getOrDefault(key, 0) val) {return false;}}return true;}
}时间复杂度 最坏情况下左右指针对s的每个元素各遍历一遍哈希表中对s中的每个元素各插入、删除一次对t中的元素各插入一次。每次检查是否可行会遍历整个t的哈希表哈希表的大小与字符集的大小有关设字符集大小为C则渐进时间复杂度为O(C⋅∣s∣∣t∣))。 空间复杂度 这里用了两张哈希表作为辅助空间每张哈希表最多不会存放超过字符集大小的键值对我们设字符集大小为C则渐进空间复杂度为O(C)。
