LeetCode76:最小覆盖子串

https://leetcode.com/problems/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).

Example:

Input: S = "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.

解决方案

滑动窗口算法

算法

1.     初始，left指针和right指针都指向SSS的第一个元素.
2.     将 right 指针右移，扩张窗口，直到得到一个可行窗口，亦即包含TTT的全部字母的窗口。
3.     得到可行的窗口后，将left指针逐个右移，若得到的窗口依然可行，则更新最小窗口大小。
4.     若窗口不再可行，则跳转至 2。

https://leetcode-cn.com/problems/minimum-window-substring/solution/76-zui-xiao-fu-gai-zi-chuan-cshuang-zhi-zhen-mo-ba/

Solution

class Solution {
public:string minWindow(string s, string t) {int count[256] = { 0 };for (auto c : t) ++count[c];int currentLen = 0;int minLength = s.length();string res;for (int l = 0, r = 0; r < s.length(); ++r){count[s[r]]--;if (count[s[r]] >= 0) ++currentLen;while (currentLen == t.length()) {if (r - l + 1 <= minLength) {minLength = r - l + 1;res = s.substr(l, r - l + 1);}count[s[l]]++;if (count[s[l]] > 0) --currentLen;++l;}}return res;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！