Simple C++ using unordered_map


  • 0
    M
       string minWindow(string s, string t) {
            int n = (int)s.size(), m = (int)t.size();
            if (n == 0 || m == 0) return "";
            unordered_map<char, int> map;
            for (char c : t)
                map[c]++;
            int k = 0;
            auto l = s.begin(), h = l;
            for (; k < m && h < s.end(); h++) {
                if (map.count(*h) > 0) {
                    if (map[*h] > 0)
                        k++;
                    map[*h]--;
                }
            }
            if (k < m) return "";
            auto lm = l, hm = h; 
            while (true) {
                while (map.count(*l) == 0 || map[*l] < 0) {
                    if (map.count(*l) > 0 && map[*l] < 0)
                        map[*l]++;
                    l++;
                }
                if (distance(l, h) < distance(lm, hm)) 
                    lm = l, hm = h;
                if (h < s.end()) {
                    if (map.count(*h) > 0) 
                        map[*h]--;
                    h++;
                } else 
                    break;
            } 
            return string(lm, hm);
        }

  • 0
    B

    In this case, unordered_map runs a bit slowly.


  • 0
    M

    Thanks for your comment! Yes, array will be quicker in this way. Please let me know any other idea.


  • 0
    M

    A faster (12ms) and cleaner version using array, and easier to follow. Thanks bethunebtj !

       string minWindow(string s, string t) {
            int ns = (int)s.size(), nt = (int)t.size();
            if (ns < nt) return "";
            int ref[256], run[256];
            fill_n(ref, 256, 0);
            for (unsigned char c : t)
                ref[c]++;
            fill_n(run, 256, 0);
            int L = ns, start = 0, nc = 0;
            for (int i = 0, j = 0; j < ns; j++) {
                unsigned char c = s[j];
                if (ref[c]) {
                    run[c]++;
                    if (run[c] <= ref[c])
                        nc++;
                }
                while (i <= j) {
                    c = s[i];
                    if (ref[c]==0) 
                        i++;
                    else if (run[c]>ref[c]) {
                        run[c]--;
                        i++;
                    } else
                        break;
                }
                if (nc == nt && j-i+1 < L) {
                    L = j-i+1;
                    start = i;
                }
            }
            if (nc == nt) 
                return s.substr(start, L);
            else
                return "";
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.