代码简单,只写简单代码
import java.util.*;
public class Solution {
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
public String minWindow (String S, String T) {
// write code here
// 字母桶, 保证覆盖
int n = S.length();
int m = T.length();
if (n == 0 || m == 0 || m > n) return "";
int[] need = new int[128];
int count = m;
for (int i = 0; i < m; i ++ ) {
need[T.charAt(i)] ++ ;
}
int l = 0, r = 0, size = n + 1;
int start = 0;
while (r < n) {
char c = S.charAt(r);
if (need[c] > 0) {
count -- ;
}
need[c] -- ;
if (count == 0) {
while (l < r && need[S.charAt(l)] < 0) {
need[S.charAt(l)] ++ ;
l ++ ;
}
if (r - l + 1 < size) {
size = r - l + 1;
start = l;
}
}
r ++ ;
}
return size == n + 1?"": S.substring(start, start + size);
}
}