leetcode:最小覆盖字符串

1笨方法

对于算法题目，自己能想到的往往是最基础的笨方法。

代码如下：

如果t的长度是len1，s的长度是len2，那么最小窗口是len1，最大窗口是len2。所以可以从len1到len2，遍历窗口大小，对于每个窗口大小，将窗口从前向后进行移动。因为窗口是从小到大进行遍历，所以第一次遇到满足条件的子串时，就可以直接范围。这种算法的时间复杂度是O(n*n)，在leetcode上运行会超时。

class Solution {
public:
    string minWindow(string s, string t) {
        std::map<char, int> tConstMap;
        std::map<char, int> tTmpMap;
        for (char c : t) {
            if (tConstMap.count(c) > 0) {
                tConstMap[c]++;
            } else {
                tConstMap[c] = 1;
            }
            tTmpMap[c] = 0;
        }

        int minWindow = t.size();
        int maxWindow = s.size();
        int maxLength = s.size();
        for (int window = minWindow; window <= maxWindow; window++) {
            for (int i = 0; i <= maxLength - window; i++) {
              for (int j = i; j < i + window; j++) {
                if (tConstMap.count(s[j]) > 0) {
                    tTmpMap[s[j]]++;
                }
              }
              bool result = true;
              for (auto [c, count] : tTmpMap) {
                if(count < tConstMap[c]) {
                  result = false;
                }
                tTmpMap[c] = 0;
              }
              if (result == true) {
                std::cout << "i:" << i <<",window:" << window <<std::endl;
                return s.substr(i, window);
              }
            }
        }
        return "";
    }
};

 针对上边的代码，我们可以看到，针对一个确定大小的window，在从前向后遍历的过程中，每次只移动了一个字符的位置，但是每次都要对tTmpMap进行清空并重新计算，完全可以只对移出窗口的元素和移入窗口的元素进行处理。但是时间复杂度仍然较高，在leetcode上运行会超时。

class Solution {
public:
    string minWindow(string s, string t) {
        std::map<char, int> tConstMap;
        std::map<char, int> tTmpMap;
        for (char c : t) {
            if (tConstMap.count(c) > 0) {
                tConstMap[c]++;
            } else {
                tConstMap[c] = 1;
            }
            tTmpMap[c] = 0;
        }

        int minWindow = t.size();
        int maxWindow = s.size();
        int maxLength = s.size();
        for (int window = minWindow; window <= maxWindow; window++) {
            for (int i = 0; i <= maxLength - window; i++) {
              if (i == 0) {
                for (auto [c, value] : tTmpMap) {
                    tTmpMap[c] = 0;
                }
                for (int j = i; j < i + window; j++) {
                    if (tConstMap.count(s[j]) > 0) {
                        tTmpMap[s[j]]++;
                    }
                }
              } else {
                if (tConstMap.count(s[i +window - 1]) > 0) {
                    tTmpMap[s[i +window - 1]]++;
                }
              }
              
              bool result = true;
              for (auto [c, count] : tTmpMap) {
                if(count < tConstMap[c]) {
                  result = false;
                  break;
                }
              }
              if (result == true) {
                return s.substr(i, window);
              }
              
              if (tTmpMap.count(s[i]) > 0) {
                tTmpMap[s[i]]--;
              }
            }
        }
        return "";
    }
};

2leetcode题解一

官方题解中没有遍历窗口的大小，而是使用双指针的方式。用窗口的左边沿和右边沿来表示一个窗口，通过左右边沿的移动来遍历不同的情况。

class Solution {
public:
    //t中字符出现的次数
    unordered_map <char, int> ori; 
    //s中字符出现的次数
    unordered_map <char, int> cnt;
    
    //判断当前子串是不是覆盖了t
    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        //t中字符出现的次数
        for (const auto &c: t) {
            ori[c]++;
        }

        int l = 0;//窗口左边沿
        int r = 0;//窗口右边沿
        int len = INT_MAX;
        int ansL = -1;
        int ansR = -1;
       
        while (r < int(s.size())) {
            //统计s中字符的数量，移动窗口右边沿
            if (ori.find(s[r]) != ori.end()) {
                cnt[s[r]]++;
            }

            //移动窗口左边沿，找到慢去条件的最小窗口
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    cnt[s[l]]--;
                }
                l++;
            }
            r++;
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

3leetcode题解二

题解二比题解一性能更高。

相同点：

①都维护了两个map，分别用于记录s和t中字符出现的次数。

②窗口右边沿的移动均是沿着s进行移动，没有其它的条件约束。

不同点：

①题解二中多了一个count，用count和t的长度是否相等来表示当前子串是不是覆盖了t。当s中的字符出现次数少于t中字符的出现次数时，对count进行递增。而题解一种使用函数check来判断当前子串是不是覆盖了t。

②窗口左边沿的移动方式不同：题解一种移动左边沿，加上check函数进行判断，比较好理解；题解二中移动左边界，是当当前字符出现的次数比t中出现的次数多的时候，才会像猴移动(如果字符在t中没有出现，在s中出现了，那么会移动；如果字符在s和t中都出现了，并且在s中出现的次数比t中多，那么也可以移动)。

class Solution {
public:
    string minWindow(string s, string t) {
        for (char c : t) {
            ht[c]++;
        }

        for (int i = 0, j = 0; i < s.size(); i++) {
            hs[s[i]]++;
            if (hs[s[i]] <= ht[s[i]]) {
                count++;
            }

            while (hs[s[j]] > ht[s[j]]) {
                hs[s[j]]--;
                j++;
            }

            if (count == t.size()) {
                 if (ret.empty() || i - j + 1 < ret.size()) {
                    ret = s.substr(j, i - j + 1);
                 }
            }
        }

        return ret;
    }

private:
  int hs[123] = {0};
  int ht[123] = {0};
  int count = 0;
  std::string ret = "";
};