刷题（1）leetcode 76: Minimum Window
在没有老人帮助带孩子的情况下，我终于还是下定决心要刷题了。希望能坚持，给同样想要刷题跳槽的小娃妈妈提供一些数据参考。
现在是哄娃睡着后的安静时间，晚上11点。加油。
第一道： leetcode 76: Minimum Window Substring
这道是hard题，题目是给出两个字符串S, T， 找出S能覆盖T所有character的最小子集。这道题目根据题目意思，S和T都是能重复character的，但是题目比较tricky的是并没有说S的一个character算不算能覆盖T中同一个Character的重复，e.g: consider S is "aa", T is "aa", the answer should be 2 instead of 1.
答题思路是sliding window.
我的解法：
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
//currentCount means the count of characters that are covered already
int left = 0, minLeft = 0, minLen = s.length() + 1, currentCount = 0;
//one can also use an array of 128 chars along with a flag array, I chose map, which is similar
//charsCount means the count of each char that still need to be covered
Map<Character, Integer> charsCount = new HashMap<>();
for(int i=0;i<t.length();i++) {
char cha = t.charAt(i);
if (charsCount.containsKey(cha)) {
charsCount.put(cha, charsCount.get(cha) + 1);
} else {
charsCount.put(cha, 1);
}
}
for(int right=0;right<s.length();right++) {
char cha = s.charAt(right);
if(charsCount.containsKey(cha)) {
//once we find that in the window there's a char covers one char in t, we increase the currentCount
int count = charsCount.get(cha);
count --;
charsCount.put(cha, count);
if(count >=0) {
currentCount++;
}
// when we find the current window can cover all the characters in t, we consider move the left pointer
while(currentCount == t.length()) {
//if it's not the min len, we don't need to record
if(right - left + 1 < minLen) {
minLeft = left;
minLen = right - left +1;
}
//when we find the left char we move out because of the move of the left pointer covers one char in t, we need to find a new one to cover that char in t later
if(charsCount.containsKey(s.charAt(left))) {
int newCount = charsCount.get(s.charAt(left)) + 1;
charsCount.put(s.charAt(left), newCount);
if(newCount > 0) {
currentCount--;
}
}
left ++;
}
}
}
return minLen > s.length() ? "" : s.substring(minLeft, minLeft + minLen);
}
}
big o for time should be O(s.length), because there's a loop of s.length, but it only iterate once, so the total time should be O(n).
big o for space should be O(t.length), because we only record the ones occur in t.
