LeetCode 笔记系列16.2 Minimum Window Substring [从O(N*M), O(NlogM)到O(N),人生就是一场不停的战斗]
题目: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.
上一个系列我们讲到了O(N*M)的解法,这里主要的矛盾是,当遇到一个合法的window的时候,我们无法找到高效的办法(最好是O(1))来找到这个window的起点。下面的O(NlogM)的解法在上一个解法的基础上,使用一个SoredMap来存放当前的window。
该map的key是S的index,value对应S中该index的字母。因为是SortedMap,在发现合法的Window后,总是能通过firstKey和lastKey得到window的长度。而且也免除了使用额外的bit_status来检验合法window的需要。
同样的,当一个字母收集超过了T中要求的数目,那么删除charAppearenceRecorder中对应链表的头节点,同时,还需删除SortedMap中该index为key的entry。代码如下:
public String minWindow2(String S, String T){
HashMap<Character, Integer> needToFill = new HashMap<Character, Integer>();
HashMap<Character, LinkedList<Integer>> charAppearenceRecorder = new HashMap<Character, LinkedList<Integer>>();
SortedMap<Integer, Character> winMap = new TreeMap<Integer, Character>();
int minWinStart = -1;
int minWinEnd = S.length();
for(int i = 0; i < T.length(); i++){
if(!needToFill.containsKey(T.charAt(i))){
needToFill.put(T.charAt(i), 1);
charAppearenceRecorder.put(T.charAt(i), new LinkedList<Integer>());
}else {
needToFill.put(T.charAt(i), needToFill.get(T.charAt(i)) + 1);
}
} for(int i = 0; i < S.length(); i++){
char c = S.charAt(i);
if(needToFill.containsKey(c)){
LinkedList<Integer> charList = charAppearenceRecorder.get(c);
if(charList.size() < needToFill.get(c)){
charList.add(i);
winMap.put(i, c);
}else {
//如果某个字母收集过了,需要删除该字母出现的最小的index,保留靠右的部分
int idxToErase = charList.removeFirst();
winMap.remove(idxToErase);
winMap.put(i, c);
charList.add(i);
}
if(winMap.size() == T.length()){
int start = winMap.firstKey();
int end = winMap.lastKey();
if(end - start < minWinEnd - minWinStart){
minWinStart = start;
minWinEnd = end;
}
}
}
} return minWinStart != -1 ? S.substring(minWinStart, minWinEnd + 1) : "";
}
O(NlogM)
代码的流程很符合O(N*M)的方法。就不“举一个栗子”了吧。
总结下:
1.合理运用embeded的数据结构。
最新文章
- hash模块 hashlib 和hmac
- tomcat部署https+TLS 1.2+Apple ATS支持
- java.lang.Boolean->;介绍
- js的事件的绑定
- Spring-JDBC实现Contact的CRUD
- Apache日志配置详解(rotatelogs LogFormat)
- LINK : fatal error LNK1104: 无法打开文件“LIBCD.lib”
- 从DNS配置
- sql 中各种锁随记
- Ember学习(8):REOPENING CLASSES AND INSTANCES
- MySQL可视化管理工具 —— Navicat for MysSQL
- poj 1011 Sticks (DFS+剪枝)
- 移动端 (基于jquery的3个)touch插件
- HNOI2017 单旋
- laravel 【error】MethodNotAllowedHttpException No message
- .NET MVC扩展UrlHelper支持CDN
- C#构造函数、私有构造函数、静态构造函数与构造函数执行顺序
- 3--Selenium环境准备--Eclipse 引入 selenium-server包
- [js高手之路]Node.js模板引擎教程-jade速学与实战1-基本用法
- 初始Winsock编程