read/MinimunWindowSubstring

Minimum Window Substring

找到字符串 S 中包含字符串 T 所有字符的最小子串

my solution

const int _ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    string minWindow(string s, string t) {
        if (t.size() > s.size()) return {};

        int had = 0;
        int b = 0, e = 0;
        string tmpt = t;
        map<char, int> used;
        for (int i = 0; i < s.size(); ++i) {
            int indx = tmpt.find(s[i]);
            if (indx == string::npos) {
                ++used[s[i]]; continue; 
            }
            tmpt.erase(tmpt.begin() + indx);

            if (had++ == 0) b = i;
            if (tmpt.size() == 0) {
                e = i; break;
            }
        }
        if (had != t.size()) return {};

        int rb = b, re = e;
        while (b < s.size()) {
            char need = s[b++];
            while (b < s.size() && t.find(s[b]) == string::npos) b++;
            if (b >= s.size()) break;

            if (used[need] > 0) { 
                if (e - b < re - rb) {
                    rb = b; re = e;
                }
                --used[need]; continue; 
            }

            while (++e < s.size() && s[e] != need)
                ++used[s[e]];

            if (e >= s.size()) break;
            else if (e - b < re - rb) {
                rb = b; re = e;
            }
        }

        return s.substr(rb, re - rb + 1);
    }
};

代码量挺大的…

简单来说, 我的想法是首先找到最左边包含所有字符的最小子串, 然后 slide window , 慢慢移动到字符 S 尾端

这样的话, 复杂度就是 O(n)

the best solution

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> hash(128, 0);
        for(auto c: t) hash[c]++;
        int count = t.size(), start = 0, end = 0, minStart, minLen = INT_MAX;
        while(end < s.size()) {
            if(hash[s[end]] > 0) count--;
            hash[s[end]]--;
            end++;

            while(count == 0) {
                if(hash[s[start]] == 0) {
                    if(end - start < minLen) {
                        minStart = start;
                        minLen = end - start;
                    }
                    count++;
                }
                hash[s[start]]++;
                start++;
            }
        }
        if(minLen == INT_MAX) return "";
        return s.substr(minStart, minLen);
    }
};

它也是类似 slide window 的做法, 不过比我简洁得多, 从实现角度上, 比我要好一些

PS : 这是 hard 难度的题, 但是做完后感觉也就那样…

是不是所有 hard 难度的题其实本质上的解决方法都不难 ? 或许我对于这些的理解还不够深刻

感觉我再加深一下, 应该就能较为轻松应对 hard 了 :) (膨胀ing… )