【leetcode刷题笔记】Minimum Window Substring
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.
题解:参考leetcode给出的解答,实现了O(n)的算法。
用到的主要变量如下:
设置一个Map:ToFind记录T中出现的字符的种类和个数,我们需要在S中找到这些字符。
设置另一个Map:hasFound记录当前窗口中包含的字符的种类和个数。
这两个Map,结合一个变量count——在当前窗口中找到的T中的字符个数,我们就可以判断当前窗口是否包含T中所有的字符了。
算法的主要过程如下:
- 当前窗口的起始和结束位置都在S(0)处;
- 当窗口中没有包含T中所有的字符时(count<T.length),扩展窗口的右端end,直到窗口中包含了T中所有的变量。
- 此时窗口不一定是最小的,因为左端还有可能缩进,根据窗口的左端变量begin所指的元素,把窗口的左端尽可能右移。
- 得到一个包含T的窗口,跟最小的窗口比较,如果比最小的窗口小,就更新最小的窗口。
举个例子:S = "acbbaca" , T = "aba"。
如上图所示,end从初始的位置扩展到下面的图中的位置时候,窗口包含了T中所有的字符,而且begin也无法挪动了,此时得到一个最小窗口长度为5;
接下来继续移动end直到下一个包含在T里面的元素处(见第二幅图),然后把begin尽可能往右移动(见第三幅图),得到一个新的当前最小窗口baca,由于它比最小窗口acbba短,所以更新最小窗口为baca。算法结束。
所以我们可以看出begin只有在找到T的时候才右移收缩窗口,而end一直后移。在找到第一个窗口后,end每移动到一个T里面包含的元素处,就会有一个新的窗口(比如上述end从索引为4的地方挪动到索引为6的地方)。
代码如下:
public class Solution {
public String minWindow(String S, String T) {
HashMap<Character, Integer> needToFind = new HashMap<Character, Integer>();
HashMap<Character, Integer> hasFound = new HashMap<Character, Integer>();
int count = 0; for(int i = 0;i < T.length();i++){
char ch_t = T.charAt(i);
if(!needToFind.containsKey(ch_t)){
needToFind.put(ch_t, 1);
hasFound.put(ch_t, 0);
}
else {
needToFind.put(ch_t, needToFind.get(ch_t)+1);
}
} int minWindowBegin = -1;
int minWindowEnd = S.length();
int minWindowLen = S.length();
for(int begin = 0,end = 0; end < S.length();end++){
char char_end = S.charAt(end);
//skip character not in T
if(!needToFind.containsKey(char_end))
continue;
hasFound.put(char_end, hasFound.get(char_end)+1);
if(hasFound.get(char_end) <= needToFind.get(char_end))
count++; if(count == T.length()){
//narrow down the window as much as possible
char char_begin = S.charAt(begin);
while(!needToFind.containsKey(char_begin) || hasFound.get(char_begin) > needToFind.get(char_begin)){
if(needToFind.containsKey(char_begin) && hasFound.get(char_begin) > needToFind.get(char_begin)){
hasFound.put(char_begin, hasFound.get(char_begin)-1);
}
begin++;
char_begin = S.charAt(begin);
} int windowLen = end - begin + 1;
if(windowLen <= minWindowLen){
minWindowBegin = begin;
minWindowEnd = end;
minWindowLen = windowLen;
} }
} if(count == T.length()){
StringBuffer sbBuffer = new StringBuffer();
for(int i = minWindowBegin;i<=minWindowEnd;i++)
sbBuffer.append(S.charAt(i));
return sbBuffer.toString();
}
else
return "";
}
}
最新文章
- 使用JDOM操作XML
- GIT常用命令备忘
- 关于dialog置于底层的问题
- JAVA基础学习之命令行方式、配置环境变量、进制的基本转换、排序法、JAVA文档生成等(1)
- 【leetcode❤python】 374. Guess Number Higher or Lower
- html部分---表单、iframe、frameset及其他字符的用法(以及name、id、value的作用与区别);
- UI2_视图切换ViewController
- 使用 rem 实现 适配各种屏幕布局
- HDU5790 Prefix 字典树+主席树
- CSS自动控制图片大小的代码
- passwd-shadow文件
- git备忘录
- iOS基础 - Quartz 2D绘图的基本步骤
- Unity 类似FingerGestures 的相机跟随功能
- spring学习笔记二 注解及AOP
- Cocos Creator JS web平台复制粘贴代码(亲测可用)
- 2.1 maven配置多镜像地址
- JavaScript实现LUHN算法验证银行卡号有效性
- Android Studio 在项目中引用第三方jar包
- 11.7 NOIP模拟赛
热门文章
- 2017-5-14 湘潭市赛 Parentheses 转化思想+贪心 使括号序列合法的最小花费。满足前面左括号的数量>;=有括号的数量。
- mySQL 开启事件存储过程
- ffmpeg中的x264编码选项,对应关系
- MySQL - 统计每个月生日的人数
- JavaScript 与 Java 是两种完全不同的语言,无论在概念还是设计上。
- Pig系统分析(8)-Pig可扩展性
- day2 python基础 while 循环补充
- windows Objective-C模拟环境搭建
- 免安装mysql配置
- 45、Android事件总线分发库的使用