五刷 07/2022
Version #1 Array as counter map + Sliding window
写了一个bug就是没有在while count== 0 的时候update答案，而是在出了while loop的时候才update，这在这道题里是不对的
求max的时候是跳过所有不符合的然后走到符合的
这道题是求min所以是跳过所有符合的until不符合的，所以要在while loop里面update
Time O(N)
Space O(256)~O(1)
Runtime: 4 ms, faster than 95.18% of Java online submissions for Minimum Window Substring.
Memory Usage: 44.1 MB, less than 65.84% of Java online submissions for Minimum Window Substring.
class Solution {
public String minWindow(String s, String t) {
// A satisfied window must could possible containing more characters than the character count in t
int[] map = new int[128];
int count = t.length(); // we need to map count number of characters
for (int i = 0; i < t.length(); i++) {
// if the count is zero, a new character is encountered
map[t.charAt(i)]++;
}
Integer resStart = null, resEnd = null;
int start = 0;
// if the number of character is decreased to less than zero, means we have matched more tha needed characters
for (int end = 0; end < s.length(); end++) {
char c = s.charAt(end);
if (map[c] > 0) {
count--;
}
map[c]--;
while (count == 0) {
if (resStart == null || end - start < resEnd - resStart) {
resStart = start;
resEnd = end;
}
c = s.charAt(start);
map[c]++;
if (map[c] > 0) {
count++;
}
start++;
}
}
return resStart == null ? "" : s.substring(resStart, resEnd + 1);
}
}
73.14 %
class Solution {
public String minWindow(String s, String t) {
int[] map = new int[256];
String result = null;
int count = t.length();
int left = -1;
for (int i = 0; i < t.length(); i++) {
map[t.charAt(i)]++;
}
// T = "ABC"
// S = "ADOBECODEBANC"
for (int right = 0; right < s.length(); right++) {
char curr = s.charAt(right);
if (map[curr] > 0) count--;
map[curr]--;
while (count == 0) {
if (result == null || right - left < result.length()) {
result = s.substring(left + 1, right + 1);
}
left++;
curr = s.charAt(left);
map[curr]++;
if (map[curr] > 0) count++;
}
}
return result == null ? "" : result;
}
}
三刷 HashMap
48.12 %
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
int total = t.length();
String result = null;
for (int i = 0; i < t.length(); i++) {
map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
}
int left = -1;
int right = 0;
// (left, right]
while (right < s.length()) {
char c = s.charAt(right);
int count;
if (map.containsKey(c)) {
count = map.get(c);
if (count > 0) {
total--;
}
map.put(c, count - 1);
}
while (total == 0 && left < right) {
if (result == null || right - left < result.length()) {
result = s.substring(left + 1, right + 1);
}
left++;
c = s.charAt(left);
if (map.containsKey(c)) {
count = map.get(c);
if (count >= 0) {
total++;
}
map.put(c, count + 1);
}
}
right++;
}
return result == null ? "" : result;
}
}
二刷
96.35 %
class Solution {
public String minWindow(String s, String t) {
int[] counter = new int[256];
int match = 0;
for (int i = 0; i < t.length(); i++) {
counter[t.charAt(i)]++;
match++;
}
int fast = 0;
int slow = 0;
int min = s.length() + 1;
int start = 0;
int end = 0;
// [slow, fast]
for (fast = 0; fast < s.length(); fast++) {
if (--counter[s.charAt(fast)] >= 0) {
match--;
}
while (match == 0) {
if (fast - slow + 1 < min) {
min = fast - slow + 1;
start = slow;
end = fast;
}
if (++counter[s.charAt(slow++)] > 0) {
match++;
}
}
}
if (min == s.length() + 1) return "";
return s.substring(start, end + 1);
}
}
一刷
Time O(length of string)
Space O(1)
2 bugs
1st I forgot to update the value of minLength by the value of currLength
2st Didn't take care of the situation that the string is not found.
public class Solution {
/**
* @param source: A string
* @param target: A string
* @return: A string denote the minimum window
* Return "" if there is no such a string
*/
public String minWindow(String source, String target) {
// write your code
if (source == null || source.length() == 0 || target == null || target.length() == 0) return "";
int[] sourceHash = new int[256];
int[] targetHash = new int[256];
//total number of target chars
int count = 0;
//Index is the ASCII number of each character
for (int i = 0; i < target.length(); i++) {
targetHash[target.charAt(i)]++;
count++;
}
int left = 0, right = 0;
//result String [start, end]
int start = 0, end = 0, minLength = Integer.MAX_VALUE;
int index;
for (right = 0; right < source.length(); right++) {
index = source.charAt(right);
if (targetHash[index] > 0) {
sourceHash[index]++;
if (targetHash[index] >= sourceHash[index]) count--;
}
while (count == 0) {
index = source.charAt(left);
int currLength = right - left + 1;
if (currLength < minLength) {
minLength = currLength;
start = left;
end = right;
}
if (targetHash[index] > 0) {
sourceHash[index]--;
if (targetHash[index] > sourceHash[index]) count++;
}
left++;
}
}
if (minLength == Integer.MAX_VALUE) return "";
return source.substring(start, end + 1);
}
}
No comments:
Post a Comment