LeetCode 题解（101）: Minimum Window Substring

本文主要是介绍LeetCode 题解（101）: 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.

题解：

双指针保持count == t.length()的移动。

c++版：

class Solution {
public:string minWindow(string s, string t) {if (s.length() < t.length())return "";int count = 0;bool found = false;int start = 0, end = 0;int distance = INT_MAX;string result ="";int needToFind[256] = { 0 }, hasFound[256] = {0};for (int i = 0; i < t.length(); i++)needToFind[t[i]]++;while (end < s.length()) {if (needToFind[s[end]] == 0) {end++;continue;}hasFound[s[end]]++;if (hasFound[s[end]] <= needToFind[s[end]])count++;if (count == t.length()) {while (needToFind[s[start]] == 0 || hasFound[s[start]] > needToFind[s[start]]) {if (hasFound[s[start]] > needToFind[s[start]])hasFound[s[start]]--;start++;}if (end - start + 1 < distance) {distance = end - start + 1;result = s.substr(start, distance);}}end++;}return result;}
};

Java版：

public class Solution {public String minWindow(String s, String t) {if(s.length() < t.length())return "";int[] hasFound = new int[256];int[] needToFind = new int[256];for(int i = 0; i < t.length(); i++) {needToFind[t.charAt(i)]++;}int distance = Integer.MAX_VALUE;int start = 0, end = 0;int count = 0;String result = "";while(end < s.length()) {if(needToFind[s.charAt(end)] == 0) {end++;continue;}hasFound[s.charAt(end)]++;if(hasFound[s.charAt(end)] <= needToFind[s.charAt(end)])count++;if(count == t.length()) {while(needToFind[s.charAt(start)] == 0 || hasFound[s.charAt(start)] > needToFind[s.charAt(start)]) {if(hasFound[s.charAt(start)] > needToFind[s.charAt(start)])hasFound[s.charAt(start)]--;start++;}if(end - start + 1 < distance) {distance = end - start + 1;result = s.substring(start, end + 1);}}end++;}return result;}
}

Python版：

import sysclass Solution:# @param {string} s# @param {string} t# @return {string}def minWindow(self, s, t):needToFind, hasFound, start, end, count, result, distance = [0] * 256, [0] * 256, 0, 0, 0, "", sys.maxintfor i in t:needToFind[ord(i)] += 1while end < len(s):if needToFind[ord(s[end])] == 0:end += 1continuehasFound[ord(s[end])] += 1if hasFound[ord(s[end])] <= needToFind[ord(s[end])]:count += 1if count == len(t):while needToFind[ord(s[start])] == 0 or hasFound[ord(s[start])] > needToFind[ord(s[start])]:if hasFound[ord(s[start])] > needToFind[ord(s[start])]:hasFound[ord(s[start])] -= 1start += 1if end - start + 1 < distance:distance = end - start + 1result = s[start: end+1]end += 1return result

这篇关于LeetCode 题解（101）: Minimum Window Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---