Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
[思路]
这道题和Substring with Concatenation of All Words思路非常类似,同样是建立一个字典,然后维护一个窗口。区别是在这道题目中,因为可以跳过没在字典里面的字符(也就是这个串不需要包含且仅仅包含字典里面的字符,有一些不在字典的仍然可以满足要求),所以遇到没在字典里面的字符可以继续移动窗口右端,而移动窗口左端的条件是当找到满足条件的串之后,一直移动窗口左端直到有字典里的字符不再在窗口里。在实现中就是维护一个HashMap,一开始key包含字典中所有字符,value就是该字符的数量,然后遇到字典中字符时就将对应字符的数量减一。算法的时间复杂度是O(n),其中n是字符串的长度,因为每个字符再维护窗口的过程中不会被访问多于两次。空间复杂度则是O(字典的大小),也就是代码中T的长度。
public String minWindow(String S, String T) { int m = S.length(), n = T.length(); Map<Character, Integer> map = new HashMap<>(); for(int i=0; i<n; i++) { char c = T.charAt(i); map.put(c, map.containsKey(c) ? map.get(c)+1 : 1); } int l = 0, r = 0; int minStart = 0, minLen = Integer.MAX_VALUE; int count = 0; for(; r < m; r++) { char rc = S.charAt(r); // right char if(!map.containsKey(rc)) continue; map.put(rc, map.get(rc)-1); if(map.get(rc) >= 0) count++; while(count == n) { int len = r-l+1; if(len < minLen) { minLen = len; minStart = l; } char lc = S.charAt(l); // left char if(map.get(lc) != null) { map.put(lc, map.get(lc)+1); if(map.get(lc)>0) { count--; } } l++; } } if(minLen > m) return ""; return S.substring(minStart, minStart+minLen); }
我们还可以用两个数组来替代HashMap。
public String minWindow(String s, String t) { int[] mapS = new int[256]; int[] mapT = new int[256]; for(char c: t.toCharArray()) { mapT[c]++; } int minLen = Integer.MAX_VALUE; int left = 0, cnt = 0; String res = ""; for(int i=0; i<s.length(); i++) { char c = s.charAt(i); if(++mapS[c] <= mapT[c]) cnt++; if(cnt == t.length()) { c = s.charAt(left); while(mapS[c] > mapT[c]) { mapS[c]--; c = s.charAt(++left); } int len = i-left+1; if(len < minLen) { minLen = len; res = s.substring(left, i+1); } } } return res; }
又重构了下以上代码:
string minWindow(string s, string t) { vector<int> vs(256), vt(256); for(char c:t) { vt[c]++; } int m = s.size(), n = t.size(); int left = 0, cnt = 0, minLen = INT_MAX; string res; for(int i=0; i<m; i++) { vs[s[i]]++; if(!vt[s[i]]) continue; if(vs[s[i]] <= vt[s[i]]) { cnt++; } if(cnt == n) { while(vs[s[left]] > vt[s[left]]) { vs[s[left]]--; left++; } int len = i-left+1; if(len < minLen) { minLen = len; res = s.substr(left, len); } } } return res; }
Reference:
https://shepherdyuan.wordpress.com/2014/08/02/minimum-window-substring/
相关推荐
leetcode76 LeetCode76_MinimumWindowSubstring
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
500195422331430LeetCode题解 - Java语言实现.zip
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...