【LeetCode-76】Minimum Window Substring 最小窗口子串

程序员文章站 2024-03-19 21:44:58

...

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).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Discuss:

问题：字符串S，目标字符串T。从S中找到一个最小子串使得此子串包含所有T中字符。

思路：时间复杂度为O(n)，一次遍历。

题目例子中的S有点长，我们换个短的 S = "ADBANC"，T = "ABC"，那么我们肉眼遍历一遍S呗，首先第一个是A，嗯很好，T中有，第二个是D，T中没有，不理它，第三个是B，嗯很好，T中有，第四个又是A，多了一个，礼多人不怪嘛，收下啦，第五个是N，一边凉快去，第六个终于是C了，那么貌似好像需要整个S串，其实不然，我们注意之前有多一个A，但么我们就算去掉第一个A，也没事，因为第四个A可以代替之，第二个D也可以去掉，因为不在T串中，第三个B就不能再去掉了，不然就没有B了。所以最终的答案就"BANC"了。通过上面的描述，你有没有发现一个有趣的现象，我们是先扩展，再收缩，就好像一个窗口一样，先扩大右边界，然后再收缩左边界，上面的例子中我们是右边界无法扩大了后才开始收缩左边界，实际上对于复杂的例子，有可能是扩大右边界，然后缩小一下左边界，然后再扩大右边界等等。这就很像一个不停滑动的窗口了，这就是大名鼎鼎的滑动窗口Sliding Window了，简直是神器啊，能解很多子串，子数组，子序列等等的问题，是必须要熟练掌握的啊！

算法：

--遍历T，将T中字符及其出现次数保存到HashMap中。

--遍历S，将S中的字符所对应的HashMap的值减一（不存在，直接赋值-1），如果减一后仍然>=0，cnt++;

--如果cnt==t.length()，首先判断当前子串长度是否小于minLen，如果是进行更新最小子串长度以及子串值。其次收缩左指针，更新HashMap中的值，如果此时值>0，那么cnt--.

Solution:

法1：使用HashMap。

public  String minWindow(String s, String t) {
        if (s==null||t==null){
            return "";
        }
        String res="";
        Map<Character,Integer> map=new HashMap<>();
        for (int i=0;i<t.length();i++){
            if (!map.containsKey(t.charAt(i))){
                map.put(t.charAt(i),0);
            }
            int j=map.get(t.charAt(i));
            map.put(t.charAt(i),j+1);
        }
        int left=0,cnt=0,minLen=Integer.MAX_VALUE;
        for (int i=0;i<s.length();i++){
            if (!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),-1);
            }else{
                int j=map.get(s.charAt(i));
                map.put(s.charAt(i),--j);
                if (j>=0)
                    ++cnt;
                while(cnt==t.length()){

                    if (minLen>i-left+1){
                        minLen=i-left+1;
                        res=s.substring(left,left+minLen);
                    }

                    int leftJ=map.get(s.charAt(left));
                    map.put(s.charAt(left),++leftJ);
                    if (leftJ>0)
                        --cnt;
                    ++left;
                }
            }
        }
        return res;
    }

法二：使用int[]。

public static String minWindow(String s, String t) {
        if (s==null||s.length()==0||t==null||t.length()==0||s.length()<t.length())
            return "";
        String res="";
        int[] tnums=new int[256];
        for (int i=0;i<t.length();i++){
            tnums[t.charAt(i)]++;
        }
        int left=0,cnt=0,minLen=Integer.MAX_VALUE;
        for (int i=0;i<s.length();i++){
            if (--tnums[s.charAt(i)]>=0){
                cnt++;
                while(cnt==t.length()){
                    if (minLen>i-left+1){
                        minLen=i-left+1;
                        res=s.substring(left,left+minLen);
                    }
                    if (++tnums[s.charAt(left)]>0)
                        cnt--;
                    left++;
                }
            }
        }
        return res;
    }

KeyWords:Sliding Window