首页 / 更多教程 / Leetcode 076. 最小覆盖子串 双指针

Leetcode 076. 最小覆盖子串 双指针

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode 076. 最小覆盖子串 双指针，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1229字，纯文字阅读大概需要2分钟。

内容图文

地址 https://leetcode-cn.com/problems/minimum-window-substring/

            给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

一个窗口内的连续数组的性质变化， 考虑用双指针来解决这个问题。
我们首先需要解决如何能快速的知道添加或者删除某个字母后 该数组的变化与样例字符串是否接近或者满足条件。这个我们采取哈希表来解决(或者使用数组 以字母的对应的asii表的索引为关键字，也是一种哈希办法)。
l r表示一段活动的字符串 我们通过查哈希表来确认是否已经包含了样例字符串里所有的字母。
如果满足，我们尝试逐步的从左边缩短l r的距离看看能不能找到更短的满足条件的字符串。
如果不满足，我们逐步的从右边扩展l r的距离 看看能否包含样例字符串。
一轮下来，我们就可以得到最短的包含样例字符串的答案了

            class
             Solution {

            public
            :


            int sample_map[256];
int inputmap[256];

bool check() {

    for (int i = 0; i < 256; i++) {
        if (inputmap[i] < sample_map[i])
            returnfalse;
    }

    returntrue;
}

string minWindow(string s, string t) {
    for (int i = 0; i < t.size(); i++) {
        int idx = t[i] - char(0);
        sample_map[idx]++;
    }
    int ans = 999999; string ansStr;

    int l = 0; int r = 0;
    inputmap[s[r]] =1;

    while (l < s.size() && r < s.size()) {
        if (check()) {
            int len = r - l + 1;
            if (len < ans) {
                ans = len; ansStr = s.substr(l, len);
            }
            //尝试从左边缩短字符串 看看是否会依旧包含样例字符串
            inputmap[s[l]]--;
            l++;
        }
        else {
            //已经不满足包含字符串了，从右边扩展字符串
            r++;
            inputmap[s[r]]++;
        }

    }


    return ansStr;
}


};

 

原文：https://www.cnblogs.com/itdef/p/12943095.html

内容总结

以上是互联网集市为您收集整理的Leetcode 076. 最小覆盖子串 双指针全部内容，希望文章能够帮你解决Leetcode 076. 最小覆盖子串 双指针所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1239831.html

来源：【匿名】