leetcode Minimum Window Substring

leetcode 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).

For example, S = "ADOBECODEBANC" T = "ABC"

Minimum window is "BANC".

Note: If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

题目地址：leetcode Minimum Window Substring

题目大意: 给定两个字符串S和T，求在S中的一个窗格，使得T中所有字母都出现。

思路：

又是two pointers的思想。一个指针指向出现的所有字符的结尾，然后用一个开头指针看看能不能将窗格变短。

可以用数组target记录t中各个字符的个数。然后扫描s，并记录当前区间[start, i]的字符个数（用count数组）。当满足count中都大于target时，说明合法，此时尝试缩短区间（start++）

C++

class Solution {
	bool check(int count[128], int target[128]) {
		for (int i = 0; i < 128; ++i)
			if (count[i] < target[i])
				return false;
		return true;
	}

public:
	string minWindow(string s, string t) {
		int count[128] = { 0 }, target[128] = { 0 };
		for (char c : t) ++target[c];

		int start = 0, ans_s = 0, ans_e = s.size() + 2;
		for (int i = 0; i < s.size(); ++i) {
			++count[s[i]];
			while (check(count, target)) {
				while (start < i && target[s[start]] == 0) 
					--count[s[start++]];

				if (i - start < ans_e - ans_s) {
					ans_s = start;
					ans_e = i;
				}
				--count[s[start++]];
			}
		}
		return ans_e - ans_s + 1 <= s.size() ? s.substr(ans_s, ans_e - ans_s + 1) : "";
	}
};

 

另一种单数组版本写法：

但其实可以只用一个数组完成。

仍用target记录t中各个字符的个数，cnt = len(t)即需要的字符个数

然后扫描s,  若target[s[i]] > 0 ，则说明s[i]是t中的字符，cnt-=1

若cnt == 0，说明从[start, i]的都在t中，满足条件，此时尝试增大start，缩小区间。

C++

class Solution {
public:
	string minWindow(string s, string t) {
		vector<int> target(128, 0);
		for (char c : t) ++target[c];

		int cnt = t.size(), start = 0;
		int ans_s = 0, ans_e = s.size() + 1;
		for (int i = 0; i < s.size(); ++i) {
			if (target[s[i]]-- > 0) //s[i] in t
				--cnt;

			while (cnt == 0) { // found [start, i] in t
				if (i - start < ans_e - ans_s) {
					ans_s = start;
					ans_e = i;
				}
				if (++target[s[start]] > 0) //s[start] is t's element
					++cnt;
				++start;
			}
		}
		int len = ans_e - ans_s + 1;
		return len <= s.size() ? s.substr(ans_s, len) : "";
	}
};

Python

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        target = [0] * 128
        for c in t: target[ord(c)] += 1

        cnt, start = len(t), 0
        ans_s, ans_e = 0, len(s) + 1

        for i in range(len(s)):
            if target[ord(s[i])] > 0:
                cnt -= 1
            target[ord(s[i])] -= 1

            while cnt == 0:
                if i - start < ans_e - ans_s:
                    ans_s, ans_e = start, i

                if target[ord(s[start])] == 0:
                    cnt += 1
                target[ord(s[start])] += 1
                start += 1
        return "" if ans_e - ans_s + 1 > len(s) else s[ans_s: ans_e + 1]

 

本文是leetcode如下的题解

• 76. Minimum Window Substring

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/