题目描述
题目链接: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 |
|
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 76.MinimumWindowSubstring.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions