XTAO's Tech Blog
0%

[Leetcode]76. Minimum Window Substring(C++)

发表于 更新于 分类于 ， 评论数：
1.8k 2 分钟

题目描述

题目链接：76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

例子

Input: “ADOBECODEBANC”, T = “ABC”
Output: “BANC”

Note

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

解题思路

这道题目是比较典型的使用滑动窗口的题目。我们用一对指针 front 和 back定义一个滑动窗口。首先通过一个哈希表 record 记录 T 中的字符及次数，并用一个变量 to_match 来表示我们当前还需要匹配的单词的个数。

接下来让 back 往后遍历进行滑动窗口的扩张，对每一位字符进行检查：

  • 如果字符在 record 中并且次数大于 0，则表示是我们需要匹配的字符，所以 to_match 减一
  • 在 record 中对当前字符的次数减一
  • 当 to_match == 0 时，表示我们已经找到所有需要匹配的字符了，这个时候移动 front 来进行滑动窗口的压缩
    • 首先判断是否比当前最短结果短，如果是则更新结果
    • 在 record 中对 front 指向的字符 c 加一
    • 如果 record[c] > 0，表示我们又有需要匹配的字符了，对 to_match 加一，跳出循环
    • 否则继续压缩

代码如下：

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
#include <string>
#include <unordered_map>
#include<bits/stdc++.h>

class Solution {
public:
    std::string minWindow(std::string s, std::string t) {
        std::unordered_map<char, int> record;
        for (char c: t) record[c]++;
        int begin = 0;              // final string begin index
        int final_length = INT_MAX; // final string length
        int to_match = t.length();  // character to be matched

        int front = 0, back = 0;    // two-pointer defining sliding window

        while (back < s.length()) { // expanding sliding window

            if (record[s[back]] > 0) {  // target char
                to_match--;
            }

            record[s[back]]--;

            while(to_match == 0) {  // now we have all needed chars in sliding window, so compress it
                int len = back - front + 1;
                if (len < final_length) {   // if current substr is shorter update final result
                    final_length = len;
                    begin = front;
                }
                record[s[front]]++;
                if (record[s[front]] > 0) to_match++;
                front++;
            }

            back++;
        }

        return final_length == INT_MAX ? "" : s.substr(begin, final_length);

    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址： 76.MinimumWindowSubstring.cpp

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions

推荐文章