leetcode Sliding Window

leetcode 76题

Posted by franki on January 12, 2021

leetcode 76题 最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例1:

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

提示：

如果 S 中不存这样的子串，则返回空字符串 ““。

如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路

滑动窗口，先移动右指针，查看当前窗口是否包含t的字符，若全部包含，收缩窗口，移动左指针，继续搜索

代码

const minWindow = (s, t) => {
    let minLen = s.length+1;
    let start = s.length;
    let missingType = 0;

    const map = {};
    for (const c of t) {
        if (!map[c]) {
            missingType++;
            map[c] = 1;
        } else {
            map[c]++;
        }
    }

    let l = 0, r = 0;
    while (r < s.length) {
        const rightChar = s[r];
        if (map[rightChar] !== undefined) map[rightChar]--;
        if (map[rightChar] === 0) missingType--;

        while (missingType === 0) {
            if (r-l+1 < minLen) {
                minLen = r-l+1;
                start = l;
            }
            const leftChar = s[l];
            if (map[leftChar] !== undefined) map[leftChar]++;
            if (map[leftChar] > 0) missingType++;
            l++;
        }
        r++;
    }

    if (start === s.length) return "";
    return s.substring(start, start+minLen);
}

复杂度分析

  • 时间复杂度: O(N)
  • 空间复杂度: O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS