• 算法leetcode｜76. 最小覆盖子串（rust重拳出击）

    文章目录

    76. 最小覆盖子串：

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

    注意：

    • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

    样例 1：

    输入：
	
	s = "ADOBECODEBANC", t = "ABC"
	
输出：
	
	"BANC"
	
解释：
	
	最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    样例 2：

    输入：
	
	s = "a", t = "a"
	
输出：
	
	"a"
	
解释：
	
	整个字符串 s 是最小覆盖子串。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    样例 3：

    输入: 
	
	s = "a", t = "aa"
	
输出: 
	
	""
	
解释:

	 t 中两个字符 'a' 均应包含在 s 的子串中，
	因此没有符合条件的子字符串，返回空字符串。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    提示：

    • m == s.length
    • n == t.length
    • 1 <= m, n <= 105
    • s 和 t 由英文字母组成

    进阶：

    你能设计一个在 o(m + n) 时间内解决此问题的算法吗？

    分析：

    • 面对这道算法题目，二当家的再次陷入了沉思。
    • 直接采用双层循环暴力解决的话，时间复杂度会比较高，恐怕过不了用例，没有去试。
    • 题目并不要求字符的顺序，只要求了每种字符的数量，那首先就想到要做计数。
    • 接下来考虑如何降低时间复杂度，每次循环都从新匹配子串是低效的，要尽可能复用，滑动窗口在这里非常合适，使用双指针，先直接移动右指针找到第一个满足条件的子串，记下长度作为备选结果，接下来移动左指针，当不满足覆盖子串的条件时就继续移动右置针直到满足覆盖子串的条件，并比较子串的长度，取较小的子串长度作为备选结果，重复该操作，直到循环遍历完毕。
    • 如何高效判断遍历的子串已经满足覆盖子串呢？字符计数这时候就要大展拳脚了，先在遍历字符串 s 之前，先对字符串 t 进行一次遍历，做初始化计数，记录下每种字符的个数（题解中这里使用了减法，使用加法也是可以的，只是后面的加减法就要变），在遍历 s 时，移动右指针就是延长了覆盖子串，同时修改计数，这里的加减法计算要和前面初始化的相反，判断计数是否为0，如果变为0则表示，这种字符的个数已经没有差异了，但是我们需要覆盖了 t 中的每一种字符，所以需要判断 26 个字符的个数是不是都够了，如果都够了，就是满足了覆盖子串，接下来就移动左指针，同时修改计数，这里的加减计算要和右指针移动的相反。
    • 当某个字符的计数变为0时，我们需要判断 26 种字符的字符个数是不是都满足了，这里就需要26次循环，是否有更高效的办法呢？我们可以额外增加一个变量记录有差异的字符种类数（记录有差异的字符数也是可以的，但是后面的逻辑会有一点区别，思想大致相同）， 初始化时顺便初始化该变量，在遍历匹配中，每当有字符计数变为0，就修改这个变量，如果这个变量变为0则表示完全覆盖，从而提高效率。
    • 只看文字可能不便理解，建议对照着熟悉的语言的题解一起看，希望可以有助学习理解。

    在这里插入图片描述

    题解：

    rust：

    impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        // 少于目标字符串中数量的字符数量
        let mut diff_char_count = 0;
        // 字符计数器
        let mut cnt = vec![0; 128];

        // 初始化
        t.as_bytes().iter().for_each(|&b| {
            // 计数减少
            cnt[b as usize] -= 1;
            if cnt[b as usize] == -1 {
                // 差异字符数增加
                diff_char_count += 1;
            }
        });

        // 覆盖子串结果信息
        let (mut ans_len, mut ans_l) = (usize::MAX, usize::MAX);

        // 开始滑动窗口
        let s_len = s.len();
        let (mut l, mut r) = (0, 0);
        while r < s_len {
            // 计数增加
            cnt[s.as_bytes()[r] as usize] += 1;

            // 向右移动右边界后，可能该字符数量没有差异了
            if cnt[s.as_bytes()[r] as usize] == 0 {
                // 差异字符数减少
                diff_char_count -= 1;
                // 差异字符数减少后可能为0了
                if diff_char_count == 0 {
                    // 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while cnt[s.as_bytes()[l] as usize] > 0 {
                        cnt[s.as_bytes()[l] as usize] -= 1;
                        l += 1;
                    }

                    // 更新结果
                    if r - l + 1 < ans_len {
                        ans_len = r - l + 1;
                        ans_l = l;
                    }

                    // 向右移动左边界，差异字符数增加
                    cnt[s.as_bytes()[l] as usize] -= 1;
                    l += 1;
                    diff_char_count += 1;
                }
            }
            r += 1;
        }

        return if ans_l == usize::MAX {
            "".to_string()
        } else {
            s[ans_l..ans_l + ans_len].to_string()
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    go：

    func minWindow(s string, t string) string {
    // 少于目标字符串中数量的字符数量
	diffCharCount := 0
	// 字符计数器
	cnt := make([]int, 128)

	// 初始化
	for _, c := range t {
		// 计数减少
		cnt[c]--
		if cnt[c] == -1 {
			// 差异字符数增加
			diffCharCount++
		}
	}

	// 覆盖子串结果信息
	ansLen, ansL := math.MaxInt32, -1

	// 开始滑动窗口
	sLen := len(s)
	l, r := 0, 0
	for r < sLen {
		// 计数增加
		cnt[s[r]]++

		// 向右移动右边界后，可能该字符数量没有差异了
		if cnt[s[r]] == 0 {
			// 差异字符数减少
			diffCharCount--
			// 差异字符数减少后可能为0了
			if diffCharCount == 0 {
				// 向右滑动左边界，直到会有差异，取满足要求的最小串
				for cnt[s[l]] > 0 {
					cnt[s[l]]--
					l++
				}

				// 更新结果
				if r-l+1 < ansLen {
					ansLen = r - l + 1
					ansL = l
				}

				// 向右移动左边界，差异字符数增加
				cnt[s[l]]--
				l++
				diffCharCount++
			}
		}
		r++
	}

	if ansL == -1 {
		return ""
	} else {
		return s[ansL : ansL+ansLen]
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    c++：

    class Solution {
public:
    string minWindow(string s, string t) {
        // 少于目标字符串中数量的字符数量
        int diffCharCount = 0;
        // 字符计数器
        int cnt[128];
        memset(cnt, 0, sizeof(cnt));

        // 初始化
        const int tLen = t.length();
        for (int i = 0; i < tLen; ++i) {
            if (--cnt[t[i]] == -1) {
                // 差异字符数增加
                ++diffCharCount;
            }
        }

        // 覆盖子串结果信息
        int ansLen = INT_MAX, ansL = -1;

        // 开始滑动窗口
        const int sLen = s.length();
        int l = 0, r = -1;
        while (++r < sLen) {
            // 向右移动右边界后，可能该字符数量没有差异了
            if (++cnt[s[r]] == 0) {
                // 差异字符数减少后可能为0了
                if (--diffCharCount == 0) {
                    // 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while (--cnt[s[l++]] >= 0) {
                        // nothing
                    }

                    // 差异字符数增加
                    ++diffCharCount;

                    // 更新结果
                    if (r - l + 2 < ansLen) {
                        ansLen = r - l + 2;
                        ansL = l - 1;
                    }
                }
            }
        }

        return ansL == -1 ? "" : s.substr(ansL, ansLen);
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    python：

    class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 少于目标字符串中数量的字符数量
        diff_char_count = 0
        # 字符计数器
        cnt = collections.defaultdict(int)

        # 初始化
        for c in t:
            # 计数减少
            cnt[c] -= 1
            if cnt[c] == -1:
                # 差异字符数增加
                diff_char_count += 1

        # 覆盖子串结果信息
        ans_len, ans_l = float("inf"), -1

        # 开始滑动窗口
        s_len = len(s)
        l, r = 0, 0
        while r < s_len:
            # 计数增加
            cnt[s[r]] += 1

            # 向右移动右边界后，可能该字符数量没有差异了
            if cnt[s[r]] == 0:
                # 差异字符数减少
                diff_char_count -= 1
                # 差异字符数减少后可能为0了
                if diff_char_count == 0:
                    # 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while cnt[s[l]] > 0:
                        cnt[s[l]] -= 1
                        l += 1

                    # 更新结果
                    if r - l + 1 < ans_len:
                        ans_len = r - l + 1
                        ans_l = l

                    # 向右移动左边界，差异字符数增加
                    cnt[s[l]] -= 1
                    l += 1
                    diff_char_count += 1
            r += 1

        return "" if ans_l == -1 else s[ans_l: ans_l + ans_len]


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    java：

    class Solution {
    public String minWindow(String s, String t) {
        // 少于目标字符串中数量的字符数量
        int diffCharCount = 0;
        // 字符计数器
        final int[] cnt = new int[128];

        // 初始化
        final int tLen = t.length();
        for (int i = 0; i < tLen; ++i) {
            if (--cnt[t.charAt(i)] == -1) {
                // 差异字符数增加
                ++diffCharCount;
            }
        }

        // 覆盖子串结果信息
        int ansLen = Integer.MAX_VALUE, ansL = -1;

        // 开始滑动窗口
        final int sLen = s.length();
        int       l    = 0, r = -1;
        while (++r < sLen) {
            // 向右移动右边界后，可能该字符数量没有差异了
            if (++cnt[s.charAt(r)] == 0) {
                // 差异字符数减少后可能为0了
                if (--diffCharCount == 0) {
                    // 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while (--cnt[s.charAt(l++)] >= 0) {
                        // nothing
                    }

                    // 差异字符数增加
                    ++diffCharCount;

                    // 更新结果
                    if (r - l + 2 < ansLen) {
                        ansLen = r - l + 2;
                        ansL = l - 1;
                    }
                }
            }
        }

        return ansL == -1 ? "" : s.substring(ansL, ansL + ansLen);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    非常感谢你阅读本文~
    欢迎【点赞】【收藏】【评论】三连走一波~
    放弃不难，但坚持一定很酷~
    希望我们大家都能每天进步一点点~
    本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

  • 相关阅读:
    【782. 变为棋盘】
    Spring Boot 中的 Redis 数据操作配置和使用
    asp.net在线考试系统+sqlserver数据库
    时序数据库Kdb
    用wpf替代winform 解决PLC数据量过大页面卡顿的问题
    PEG 衍生物Biotin-PEG1-OH(cas:95611-10-2，2-生物素氨基乙醇)优势说明
    述职报告写作总结
    提高内外部协同效率的软件
    linux总结
    如何找回这个辅助窗口
  • 原文地址：https://blog.csdn.net/leyi520/article/details/132664640