【LeetCode热题100】【子串】最小覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""

先用一个哈希表记录目标字符串target的字符种类及其数量，然后用一个滑动窗口从字符串source上滑过去，i负责起点缩减，j负责终点延申，碰到一个字符，更新它在哈希表里面的数量减一，表示已经找到一个，当数量减到0，表示这个字符已经收集完毕，需要收集的种类数量减一

如果s[i]在哈希表里面的数量小于0，说明s[i]已经多了，i可以往前缩减滑动字符串的长度

当需要收集的字符串的种类已经为0，说明已经找到了，比较和先前找到的长度看是否需要更新

代码语言：javascript复制

class Solution {
public:
    string minWindow(string s, string t) {
        string ans = "";
        unordered_map<char, int> hash;
        for (auto &c: t)  hash[c];
        size_t need = hash.size();
        for (int i = 0, j = 0; s[j];   j) {
            if (--hash[s[j]] == 0)need--;
            while (hash[s[i]] < 0)  hash[s[i  ]];
            if (need == 0 && (ans.empty() || ans.size() > j - i   1))
                ans = move(s.substr(i, j - i   1));
        }
        return ans;
    }
};

string 字符串 hash leetcode size

0 人点赞