网站制作的公司有哪些,企业网站备案代理商,免费手机app制作,晋江网站建设洛阳网站制作目录 1.题目2.答案3.提交结果截图 链接#xff1a; 76. 最小覆盖子串 1.题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 。
注意#xff1a;
对于 t 中重复字… 目录 1.题目2.答案3.提交结果截图 链接 76. 最小覆盖子串 1.题目
给你一个字符串 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.lengthn t.length1 m, n 10^5s 和 t 由英文字母组成
进阶 你能设计一个在 o(mn) 时间内解决此问题的算法吗 2.答案
class Solution {public String minWindow(String s, String t) {// 初始化MapCharacter, Integer tMap new HashMap();char[] tChars t.toCharArray();for (char tChar : tChars) {tMap.put(tChar, tMap.getOrDefault(tChar, 0) 1);}// 遍历sint l 0;int minLength s.length() 1;int minL 0;int minR 0;char[] sChars s.toCharArray();MapCharacter, Integer windowMap new HashMap();for (int r 0; r sChars.length; r) {// 右边移动windowMap.put(s.charAt(r), windowMap.getOrDefault(s.charAt(r), 0) 1);while (checkContains(tMap, windowMap)) {if (r - l 1 minLength) {minLength r - l 1;minL l;minR r;}// 左边移动int count windowMap.get(s.charAt(l)) - 1;if (count 0) {windowMap.remove(s.charAt(l));} else {windowMap.put(s.charAt(l), count);}l;}}return minLength s.length() 1 ? : s.substring(minL, minR 1);}private boolean checkContains(MapCharacter, Integer tMap, MapCharacter, Integer window) {for (Map.EntryCharacter, Integer tEntry : tMap.entrySet()) {if (window.getOrDefault(tEntry.getKey(), 0) tEntry.getValue()) {return false;}}return true;}
}3.提交结果截图 整理完毕完结撒花~
