首页 / 面试题 / 文章

高频面试算法题：如何求解最小覆盖子串问题

面试题 潘老师 原 22小时前 16 ℃ (0) 扫码查看

前端面试算法题中最小覆盖子串问题出现频率颇高，今天，咱们就来深入探讨这道题，并且会详细讲讲解题过程中用到的Map数据结构。要是你对Map不太熟悉，也别担心，下面会先介绍相关知识，再进入正题。

一、Map数据结构基础

（一）Map是什么

Map是JavaScript里一种用于存储键值对的集合。它和JavaScript中的普通对象有点像，但又存在一些重要差异：

  • 键的类型：普通对象的键只能是字符串或者Symbol类型，而Map的键可以是任意数据类型，像对象、函数以及其他原始类型都没问题。
  • 键的顺序：Map会记住键的插入顺序，遍历Map时，元素的顺序和插入时一致；普通对象则不保证键的顺序。
  • 原型继承：Map没有原型，这样就不会意外获取到原型链上不属于它自身的数据。普通对象会从原型链继承属性和方法，可能引发一些意想不到的问题。
  • 获取大小：使用size属性就能轻松获取Map的大小，也就是键值对的数量，不像普通对象还得手动计算。
  • 性能：在频繁添加和删除键值对的场景下，Map的性能通常比普通对象更优。

（二）创建Map对象

创建Map对象有两种常见方式：

// 创建一个空Map
const myMap = new Map();

// 创建一个包含初始键值对的Map (二维数组)
const myMapWithValues = new Map([
    ['key1', 'value1'],
    ['key2', 'value2'],
    [123, 'number_key']
]);

上述代码中，第一种方式创建了一个空的Map；第二种方式通过传入一个二维数组，初始化了一个包含特定键值对的Map 。

（三）Map的常用方法

  1. set(key, value)：用于添加或更新键值对。如果键不存在，就添加新的键值对；如果键已存在，则更新对应的值。
const myMap = new Map();
myMap.set('name', 'Alice');
myMap.set('age', 30);
myMap.set('name', 'Bob'); // 更新 'name' 的值

console.log(myMap); // Map(2) { 'name' => 'Bob', 'age' => 30 }
  1. get(key)：根据传入的键获取对应的值。要是键不存在，就返回undefined。
const myMap = new Map([['name', 'Charlie'], ['city', 'London']]);
console.log(myMap.get('name'));   // 输出: Charlie
console.log(myMap.get('city'));   // 输出: London
console.log(myMap.get('country')); // 输出: undefined (键不存在)
  1. has(key)：用来检查Map中是否包含指定的键，包含就返回true，否则返回false。
const myMap = new Map([['a', 1], ['b', 2]]);
console.log(myMap.has('a')); // 输出: true
console.log(myMap.has('c')); // 输出: false
  1. delete(key)：删除指定键值对。如果删除成功，返回true；键不存在时，返回false。
const myMap = new Map([['x', 10], ['y', 20]]);
console.log(myMap.delete('x')); // 输出: true (删除成功)
console.log(myMap.delete('z')); // 输出: false (键不存在)
console.log(myMap);             // Map(1) { 'y' => 20 }
  1. clear()：清空Map，让它变成一个空的Map。
const myMap = new Map([['p', 100], ['q', 200]]);
myMap.clear();
console.log(myMap); // Map(0) {}
  1. size：获取Map的大小，也就是键值对的数量。
const myMap = new Map([['apple', 1], ['banana', 2], ['cherry', 3]]);
console.log(myMap.size); // 输出: 3

（四）遍历Map

Map提供了多种遍历方式：

  1. keys()：获取所有键的迭代器，通过遍历这个迭代器，可以获取Map中所有的键。
const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]);
for (const key of myMap.keys()) {
    console.log(key); // 输出: a, b, c
}
  1. values()：获取所有值的迭代器，用于遍历获取Map中所有的值。
const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]);
for (const value of myMap.values()) {
    console.log(value); // 输出: 1, 2, 3
}
  1. entries()：获取所有键值对的迭代器，返回的是[key, value]数组形式，方便同时获取键和值。
const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]);
for (const [key, value] of myMap.entries()) {
    console.log(key, value); // 输出: a 1, b 2, c 3
}
  1. forEach(callbackFn, thisArg)：和数组的forEach类似，对Map中的每一个键值对执行传入的回调函数。
const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]);
myMap.forEach((value, key) => {
    console.log(key, value); // 输出: a 1, b 2, c 3
});

（五）Map的应用场景

Map在实际开发中有很多用途：

  • 缓存：可以把计算结果存到Map里，这样遇到相同的计算时，直接从Map取结果，避免重复计算，提升程序效率。
  • 键值对存储：当键的类型不确定，尤其是可能为对象时，Map比普通对象更适用。
  • 维护插入顺序：在需要保证键的插入顺序的场景中，Map就派上用场了。
  • 统计词频：利用Map能很方便地统计每个词出现的次数。
  • 存储元数据：可以存储与DOM元素或其他对象相关的额外信息。

（六）Map与Object的选择

选择Map还是普通对象，可以参考以下原则：如果键始终是字符串或Symbol类型，并且对键的顺序没有要求，普通对象可能更简单；要是键的类型不确定，或者需要维护键的顺序，又或者频繁进行添加和删除键值对的操作，Map通常是更好的选择。

二、最小覆盖子串题目解析

（一）题目描述

给定两个字符串s和t，要求返回s中涵盖t所有字符的最小子串。如果s里不存在涵盖t所有字符的子串，就返回空字符串"" 。需要注意：

  • t中若有重复字符，寻找的子字符串中该字符数量不能少于t中该字符数量。
  • 若s中存在满足条件的子串，确保它是唯一答案 。

下面来看几个示例：

  • 示例1：
输入： s = "ADOBECODEBANC", t = "ABC"
输出： "BANC"
解释： 最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
  • 示例2：
输入： s = "a", t = "a"
输出： "a"
解释： 整个字符串 s 是最小覆盖子串。
  • 示例3：
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

另外，题目还给出了一些限制条件：

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

进阶要求是设计一个能在o(m+n)时间内解决此问题的算法。

（二）题解：滑动窗口算法

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if (!s || !t || s.length === 0 || t.length === 0) {
        return "";
    }

    const tMap = new Map(); // 存储 t 中每个字符出现的次数
    for (const char of t) {
        tMap.set(char, (tMap.get(char) || 0) + 1);
    }

    let left = 0; // 滑动窗口的左指针
    let right = 0; // 滑动窗口的右指针
    let minLen = Infinity; // 最小子串的长度，初始化为无穷大
    let start = 0; // 最小子串的起始位置

    let matched = 0; // 记录窗口中满足 t 字符数量的字符个数

    const windowMap = new Map(); // 存储滑动窗口中每个字符出现的次数

    while (right < s.length) {
        const char1 = s[right]; // 获取右指针指向的字符
        if (tMap.has(char1)) {
            // 如果该字符是 t 中需要的字符
            windowMap.set(char1, (windowMap.get(char1) || 0) + 1); // 更新窗口中该字符的数量
            if (windowMap.get(char1) === tMap.get(char1)) {
                // 如果窗口中该字符的数量已经满足 t 中该字符的数量，则 matched 加 1
                matched++;
            }
        }
        right++; // 右指针右移

        // 当窗口中所有 t 中的字符都满足数量时，尝试缩小窗口
        while (matched === tMap.size) {
            // 更新最小子串
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }

            const char2 = s[left]; // 获取左指针指向的字符
            if (tMap.has(char2)) {
                // 如果该字符是 t 中需要的字符
                windowMap.set(char2, windowMap.get(char2) - 1); // 窗口中该字符的数量减 1
                if (windowMap.get(char2) < tMap.get(char2)) {
                    // 如果窗口中该字符的数量小于 t 中该字符的数量，则 matched 减 1
                    matched--;
                }
            }
            left++; // 左指针右移，缩小窗口
        }
    }

    // 如果 minLen 没有被更新，则说明没有找到符合条件的子串
    return minLen === Infinity ? "" : s.substring(start, start + minLen);
};

1. 核心思想

这个算法运用了滑动窗口的思想。简单来说，就是在字符串s上维护一个动态大小的窗口，通过不断移动窗口的左右指针，在s中寻找满足条件的最小子串。这里的条件是窗口要包含字符串t中的所有字符，并且每个字符的数量不能少于t中对应字符的数量。

2. 详细步骤

  • 初始化：
    • 进行空值检查：如果s或t为空，直接返回空字符串"" ，因为空字符串肯定不存在满足条件的子串。
    • 创建tMap：使用Map存储字符串t中每个字符出现的次数，这是后续判断窗口是否满足条件的重要依据。
    • 初始化窗口指针：设置滑动窗口的左指针left为0，右指针right也为0 。
    • 初始化结果变量：把minLen设为Infinity（无穷大），用于记录最小子串的长度；start设为0，用来标记最小子串的起始位置。
    • 初始化匹配计数器：设置matched为0，它用来记录窗口中满足t字符数量要求的字符个数。
    • 创建windowMap：使用Map存储滑动窗口中每个字符出现的次数。
  • 扩展窗口 (移动右指针)：
    • while (right < s.length)循环：不断移动右指针right遍历字符串s，每次循环都尝试扩大窗口。
    • 获取当前字符：用char1 = s[right]获取right指针指向的字符。
    • 检查字符是否在tMap中：通过if (tMap.has(char1))判断该字符是否是目标字符串t中需要的字符。
    • 更新windowMap：如果是需要的字符，就更新windowMap中该字符的计数。
    • 更新matched：当windowMap中该字符的计数和tMap中该字符的计数相等时，说明窗口中该字符的数量满足要求，matched加1。
    • 右指针右移：执行right++，扩大窗口。
  • 收缩窗口 (移动左指针)：
    • while (matched === tMap.size)循环：当matched等于tMap.size时，表明当前窗口已经包含了t中所有字符且数量满足要求，此时尝试缩小窗口，看能否找到更小的覆盖子串。
    • 更新最小子串信息：如果当前窗口的长度(right - left)小于minLen ，就更新minLen和start，记录下更小的覆盖子串。
    • 获取左指针字符：用char2 = s[left]获取left指针指向的字符。
    • 检查字符是否在tMap中：同样通过if (tMap.has(char2))判断。
    • 更新windowMap：如果是需要的字符，将windowMap中该字符的数量减1。
    • 更新matched：若窗口中该字符的数量小于tMap中该字符的数量，matched减1，表示不再满足覆盖要求。
    • 左指针右移：执行left++，缩小窗口。
  • 返回结果：
    • 如果minLen仍然是Infinity，说明在遍历完整个s后，都没有找到满足条件的子串，返回空字符串""。
    • 否则，使用s.substring(start, start + minLen)提取最小子串并返回。

3. 特别注意

Map的使用：正确运用Map的has、get和set方法是解题的关键。Map让字符计数和查找变得高效，方便判断窗口内字符的情况。
matched计数器的维护：matched计数器是算法的核心部分，它精确记录了窗口中已满足要求的字符种类数量。在更新windowMap和tMap时，要确保matched的增减与它们的状态同步。
窗口收缩的条件：只有当matched === tMap.size时，才可以收缩窗口；否则，需要继续扩展窗口，直到覆盖所有需要的字符。
更新最小子串的时机：只有在matched === tMap.size的情况下，才去检查并更新minLen和start 。
边界条件处理：要注意处理空字符串的情况，以及没有找到满足条件子串时的返回值。
重复字符的处理：算法能够正确处理t中包含重复字符的情况。windowMap和tMap存储了字符的精确数量，保证窗口中字符数量符合要求。

示例图解

三、总结

通过以上对Map数据结构的介绍以及最小覆盖子串题目的详细解析，相信大家对这道高频面试算法题有了更深入的理解。在实际解题过程中，掌握好滑动窗口算法的思路，合理运用Map来处理字符计数等问题，就能顺利解决这类题目。

版权声明：本站文章，如无说明，均为本站原创，转载请注明文章来源。如有侵权，请联系博主删除。
本文链接：https://www.panziye.com/ms/17955.html
喜欢 (0)赏
【请潘老师喝杯Coffee吧！】
分享 (0)

相关文章

用户头像
发表我的评论
取消评论
表情 贴图 签到 代码

Hi，您需要填写昵称和邮箱！

  • 昵称【必填】
  • 邮箱【必填】
  • 网址【可选】