图片 1Screenshot
from 2016-01-30 19:45:26.png

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

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

Description

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 empty string “”.

If there are multiple such windows, you are guaranteed that there will
always be only one unique minimum window in S.

原题: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 empty string “”.
If there are multiple such windows, you are guaranteed that there will
always be only one unique minimum window in S.

My code:

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

For example,
S = "ADOBECODEBANC"
T = "ABC"

思路

  • 刚开始自己用unordered_map写了一个出来,159ms…
  • 往上找了一个,用两个hash数组做的,确实比我叼。

解题报告

本题求包含t字符串的最小子串,与第209题很相像,同样是定义左右两个指针。先找到一个符合标准的子串,然后分别移动左右指针,得到符合标准的最小子串。

public class Solution { public String minWindow(String s, String t) { if (s == null || s.length() == 0 || t == null || t.length return ""; HashMap<Character, Integer> tracker = new HashMap<Character, Integer>(); for (int i = 0; i < t.length { if (!tracker.containsKey(t.charAt tracker.put(t.charAt; else tracker.put(t.charAt, tracker.get(t.charAt; } int minLen = Integer.MAX_VALUE; String minStr = ""; int start = 0; int counter = 0; int i = 0; HashMap<Character, Integer> cmp = new HashMap<Character, Integer>(); while (i < s.length { char curr = s.charAt; if (tracker.containsKey { if (!cmp.containsKey cmp.put; else cmp.put(curr, cmp.get + 1); if (cmp.get <= tracker.get counter++;

题意:在字符串S中找到包含所有字符串T中字符的最短子串,如果找不到返回空字符串。T中可能存在重复字符,如aac,此时S中的最短子串中必须也要有两个a。

Minimum window is "BANC".

代码

  • unordered_map

    class Solution {
    public:
     string minWindow(string s, string t) {
        int slen = s.size(), tlen = t.size();
        if (slen == 0 || tlen == 0) return "";
    
        string res = "";
        int start = 0, end = -1;
        int i = 0;
        unordered_map<char, int> tMap;
        unordered_map<char, int> cMap;
        unordered_map<char, int> helpMap;
    
        for (i = 0; i < tlen; ++i)
            tMap[t[i]]++;
    
        i = 0;
        while (i < slen){
            if (tMap.find(s[i]) == tMap.end())
                i++;
            else break;
        }
    
        start = i;
    
        while (i < slen){
            if (tMap.count(s[i]) > 0){
                helpMap[s[i]]++;
                if (tMap[s[i]] > cMap[s[i]])
                    cMap[s[i]]++;
            }
    
            if (tMap == cMap){
                do{
                    if (res == "" || res.size() > (i - start + 1)){
                        res = s.substr(start, i - start + 1);
                    }
    
                    if (cMap[s[start]] > 1)
                        cMap[s[start]]--;
                    else cMap.erase(s[start]);
    
                    if (helpMap[s[start]] > 1)
                        helpMap[s[start]]--;
                    else helpMap.erase(s[start]);
    
                    if (helpMap[s[start]] > cMap[s[start]])
                        cMap[s[start]]++;
    
                    int j = start + 1;
                    while (j <= i){
                        if (tMap.find(s[j]) == tMap.end())
                            j++;
                        else break;
                    }
    
                    start = j;
                } while (cMap == tMap);
            }
    
            i++;
        }
    
        if (tMap == cMap && (res == "" || res.size() > (slen - start)))
                res = s.substr(start, i - start + 1);
        return res;
    }
    };
    
  • hash数组

    class Solution {
    public:
       string minWindow(string s, string t) 
    {
        string res;
        if (s.size() < t.size()) return res;
        vector<int> flag(256, 0);
        vector<int> hash(256, 0);
        for(int i = 0; i < t.size(); ++i){
            flag[t[i]]++;
            hash[t[i]]++;
        }
    
        int count = 0;
        int start = 0, minsize = s.size() + 1, minflag = -1;
        for(int i = 0; i < s.size(); ++i){
            if(flag[s[i]] > 0){
                if(--hash[s[i]] >= 0)  //这个地方
                   count++;
    
               while(count == t.size()){
                    if(i - start + 1 < minsize){
                       minsize = i - start + 1;
                       minflag = start;
                   }
    
                   //这个地方,思路确实巧妙,不得不服
                   if(flag[s[start]] > 0){
                       if(++hash[s[start]] > 0)
                            --count;
                   }
                   ++start;
               }
            }
    
        }
    
        if(minsize > s.size()) return "";
        return s.substr(minflag, minsize);
    }
    };
    

解题思路

1、定义一个hashMap,存储t中的元素和出现的次数,定义count变量。
2、定义count变量,存储t的长度。
右侧指针向后移动当count为零的时候,说明左右指针之间的substring是符合标准的一个子串。
3、移动左指针,直到两个指针之间的substring不完全包含t
4、循环直到找到最小的子串。

这道题木和

自己的思路是用一个整型数组作为map存T中包含的字符,遍历S,用一个队列存遍历过的字符,如果字符在map中并且值大于0,就将这个值减一,当这个map中所有值都是0的时候,就找到了一个包含T的子串。考虑后觉得每次都check一次map,效率很低,想到可以用一个count计数来判断。但是这个做法有个问题,就是无法缩短队列,更新最短长度。

Note:
If there is no such window in S that covers all characters in T, return
the empty string "".

代码

class Solution {
    public String minWindow(String s, String t) {
        int start = 0;
        int end = 0;
        char[] sum = s.toCharArray();
        char[] sub = t.toCharArray();
        HashMap<Character, Integer> temp = new HashMap<>();
        String result = s + " ";
        int count = sub.length;
        for (int i = 0; i < sub.length; i++) {
            if (temp.containsKey(sub[i]) ) {
                temp.put(sub[i], temp.get(sub[i]) + 1);
            } else {
                temp.put(sub[i], 1);
            }
        }

        while (end < s.length()) {
            if (temp.containsKey(sum[end]) ) {
                int flag = temp.get(sum[end]);
                if(flag > 0){//防止s与t中字符多对一的情况
                    count--;
                }
                temp.put(sum[end], --flag);//如果s中包含t的某个字符,在temp中减去
            }
            end++;
            //System.out.println("end" + end + "count:" + count + "start:" + start);
            //System.out.println("reuslt:" + result);
            if (count == 0) {
                while (start < end && count == 0) {
                    if (temp.containsKey(sum[start])) {//start 指向的字符是t中的字符
                        int flag = temp.get(sum[start]);
                       // System.out.println("flag:" + flag);
                        if (flag >= 0) {   //如果flag<0说明子串中还有该元素
                            count++;
                            result = result.length() > end - start ? s.substring(start, end) : result;

                        }
                        temp.put(sum[start], flag + 1);
                    }
                    start++;
                }
            }
            //System.out.println("result:" + result);
        }
        return result.length() ==s.length() + 1 ? "" : result;
    }
  1. Substring with Concatenation of All Words

最后查看discuss的解法后发现:
1、用map的思路是一样的。但是正解没有用队列来存储字符串,而是通过两个指针来表示;
2、不是只更新map中T含有的字符的值,而是对所有遍历到的S的字符,都对map做–操作。这样在更新左指针的时候,只要相应的++就可以了。

If there are multiple such windows, you are guaranteed that there will
always be only one unique minimum window in S.

总结

我认为这道题的难点在于,对s中重复字符的判断。所以,temp中value记录实是s与t中对应key元素的差值。当temp中value大于0,说明s的子串中没有这个key元素;当value小于0,说明s中key元素的个数是多余t的。因此这一点要认识清楚。

区别在于,窗口内,也可以存在无意义的字母,既可以不在string
t里面,也可以重复的元素。主要就是可以出现重复的元素,即 cmp.get >
tracker.get;不需要再用一个while循环去删除重复元素。这道题木也是可以用一个hashmap来做的,但可能会烦一些。

public String minWindow(String s, String t) {
    if (s == null || s.length() == 0) {
        return "";
    }

    int[] map = new int[256];
    for (int i = 0; i < t.length(); i++) {
        map[t.charAt(i)]++;
    }

    int count = t.length(), head = 0, begin = 0, end = 0, min = Integer.MAX_VALUE;
    while (end < s.length()) {
        if (map[s.charAt(end)] > 0) {
            count--;
        }
        map[s.charAt(end)]--;

        while (count == 0) {
            if (end - begin + 1 < min) {
                min = end - begin + 1;
                head = begin;
            }

            if (map[s.charAt(begin)] == 0) {
                count++;
            }
            map[s.charAt(begin)]++;
            begin++;
        }

        end++;
    }

    return min > s.length() ? "" : s.substring(head, head + min);
}

我们最开始先扫描一遍T,把对应的字符及其出现的次数存到哈希表中。

这种高难度的sliding
window题目,针对与字符串,解法归纳如下。首先声明一个HashMap tracker
来记录整个字符串的情况。其次设置一个HashMap cmp
作为和tracker的比较。设置一个start, 作为窗口的左端。设置一个i,
作为窗口的右端。固定住start后,不断地移动
i,扩展窗口,直到满足要求。或者碰到,一个元素,导致窗口的左半部分不满足要求。于是开始不断地移动start,缩小窗口,直到满足要求。然后继续移动i,当满足要求时,记录。然后移动start。接着继续移动i,寻找下一个合适的窗口。思想差不多就这样的。参考网页:

然后开始遍历S,遇到T中的字符,就把对应的哈希表中的value减一,直到包含了T中的所有的字符,纪录一个字串并更新最小字串值。

实习好难找啊,好难找啊。国内的实习也要开始关注了。北京不想去。杭州,上海,深圳。阿里巴巴,腾讯,简书,网易。你们要我吗?想想自己也是什么都不会啊。。。盯着个藤校的牌子。但真的开发技能太缺乏,只对Java有些了解。竞争实力可能连专科学生都不如。妈的。

将子窗口的左边界向右移,略掉不在T中的字符,如果某个在T中的字符出现的次数大于哈希表中的value,则也可以跳过该字符。

Anyway, Good luck, Richardo!

代码:

My code:

public class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> tmap = new HashMap<Character,Integer>();
        char[] tc = t.toCharArray();
        for(int i=0;i<tc.length;i++){ //将t转为数组后每一个字母作为键值放到hashmap中,出现的次数是其value值
            if(tmap.containsKey( tc[i] )){
                tmap.put( tc[i],tmap.get(tc[i])+1 );              
            }
            else{
                tmap.put( tc[i],1 );
            }
        }
        int left = 0,scond = 0;
        int count = 0;
        String ans = "";
        int minlen = s.length()+1;
        char []sc = s.toCharArray();
        for(int right = 0;right<s.length();right++){
            char rc = sc[right];  //right 对应的字符串
            if(tmap.containsKey( rc ) ){
                tmap.put( rc,tmap.get(rc)-1 );//窗口中出现一次该字母 ,value值-- 
                if( tmap.get(rc) >=0  ) //当在窗口中出现的次数小于在t中出现的次数时=,说明还不多于
                    count++;
                while(count == t.length()){ // 当count等于t的长度时,做两件事,一left右移动,跳过不在t中出现的字符,或者出现次数多于t的
                    if( right-left+1 < minlen ){  //二:判断并更新最小窗口的值 和ans
                        ans = s.substring(left,right+1);
                        minlen = right-left+1;
                    }
                    char lc = sc[left]; //left对应的字符串
                    if( tmap.containsKey( lc ) ){
                        tmap.put( lc,tmap.get( lc )+1 );
                        if(tmap.get( lc ) >0 )
                            count--;
                    }
                    left++;
                }
            }
        }
        return ans;
    }
}
public class Solution { public String minWindow(String s, String t) { if (s == null || t == null) { return ""; } HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int counter = t.length(); int end = 0; int start = 0; int minLen = Integer.MAX_VALUE; String ret = ""; for (int i = 0; i < s.length { map.put(s.charAt; } for (int i = 0; i < t.length { char curr = t.charAt; if (!map.containsKey { return ""; } else { map.put(curr, map.get + 1); } } while (end < s.length { char curr = s.charAt; if (map.get > 0) { counter--; } map.put(curr, map.get - 1); while (counter == 0) { // window is finished, then we need to check whether we can narrowize this window if (minLen > end - start + 1) { minLen = end - start + 1; ret = s.substring(start, end + 1); } char leftMost = s.charAt; map.put(leftMost, map.get + 1); if (map.get > 0) { counter++; } start++; } end++; } return ret; }}

 

reference:

这道题目并没能自己做出来。他的具体思路是,首先移动 end,
找到一个完整的window注意,这个window,可能存在冗余。当我们找到一个完整的window时(counter
== 0),开始移动start,减少这个冗余,拿到最短的window length(counter > 0
stop)

一直如此循环下去。

这就是window 类题目的特点,仔细看这几道题目。

Minimum Window Substring

Longest Substring with At Most K Distinct Characters

Longest Substring with At Most Two Distinct Characters

Longest Substring Without Repeating Characters

Anyway, Good luck, Richardo! — 09/19/2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图