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

叶茂林

发布于 2024-04-22 09:11:38

670

发布于 2024-04-22 09:11:38

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

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

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

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

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;
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除

string