【leetcode刷题笔记】Minimum Window Substring

2020-12-13 05:27

阅读：444

标签：style blog http color os strong io 2014

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
此时窗口不一定是最小的，因为左端还有可能缩进，根据窗口的左端变量begin所指的元素，把窗口的左端尽可能右移。
得到一个包含T的窗口，跟最小的窗口比较，如果比最小的窗口小，就更新最小的窗口。

举个例子：S = "acbbaca" , T = "aba"。

soscw.com,搜素材

如上图所示，end从初始的位置扩展到下面的图中的位置时候，窗口包含了T中所有的字符，而且begin也无法挪动了,此时得到一个最小窗口长度为5；

soscw.com,搜素材

接下来继续移动end直到下一个包含在T里面的元素处（见第二幅图），然后把begin尽可能往右移动（见第三幅图），得到一个新的当前最小窗口baca，由于它比最小窗口acbba短，所以更新最小窗口为baca。算法结束。

所以我们可以看出begin只有在找到T的时候才右移收缩窗口，而end一直后移。在找到第一个窗口后，end每移动到一个T里面包含的元素处，就会有一个新的窗口（比如上述end从索引为4的地方挪动到索引为6的地方）。

代码如下：

 1 public class Solution {
 2     public String minWindow(String S, String T) {
 3         HashMap needToFind = new HashMap();
 4         HashMap hasFound = new HashMap();
 5         int count = 0;
 6         
 7         for(int i = 0;i ){
 8             char ch_t = T.charAt(i);
 9             if(!needToFind.containsKey(ch_t)){
10                 needToFind.put(ch_t, 1);
11                 hasFound.put(ch_t, 0);
12             }
13             else {
14                 needToFind.put(ch_t, needToFind.get(ch_t)+1);
15             }
16         }
17         
18         int minWindowBegin = -1;
19         int minWindowEnd = S.length();
20         int minWindowLen = S.length();
21         for(int begin = 0,end = 0; end ){
22             char char_end = S.charAt(end);
23             //skip character not in T
24             if(!needToFind.containsKey(char_end))
25                 continue;
26             hasFound.put(char_end, hasFound.get(char_end)+1);
27             if(hasFound.get(char_end)  needToFind.get(char_end))
28                 count++;
29             
30             if(count == T.length()){
31                 //narrow down the window as much as possible
32                 char char_begin = S.charAt(begin);
33                 while(!needToFind.containsKey(char_begin) || hasFound.get(char_begin) > needToFind.get(char_begin)){
34                     if(needToFind.containsKey(char_begin) && hasFound.get(char_begin) > needToFind.get(char_begin)){
35                         hasFound.put(char_begin, hasFound.get(char_begin)-1);
36                     }
37                     begin++;
38                     char_begin = S.charAt(begin);
39                 }
40                 
41                 int windowLen = end - begin + 1;
42                 if(windowLen  minWindowLen){
43                     minWindowBegin = begin;
44                     minWindowEnd = end;
45                     minWindowLen = windowLen;
46                 }
47                     
48             }
49         }
50         
51         if(count == T.length()){
52             StringBuffer sbBuffer = new StringBuffer();
53             for(int i = minWindowBegin;i)
54                 sbBuffer.append(S.charAt(i));
55             return sbBuffer.toString();
56         }
57         else
58             return "";        
59     }
60 }

【leetcode刷题笔记】Minimum Window Substring,搜素材,soscw.com

【leetcode刷题笔记】Minimum Window Substring

标签：style blog http color os strong io 2014

原文地址：http://www.cnblogs.com/sunshineatnoon/p/3870054.html

上一篇：Microsoft.Aspnet.Snapin 命名空间

下一篇：php基础学习

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【leetcode刷题笔记】Minimum Window Substring
文章链接：http://soscw.com/essay/31048.html

亲，登录后才可以留言！

【leetcode刷题笔记】Minimum Window Substring

评论

热门文章

推荐文章

最新文章

置顶文章