题目:
题目理解:这题属于最小滑动窗口。所求得的连续滑动窗口包含来t中的字符,不一定要按照t中的顺序。
class Solution {
public String minWindow(String s, String t) {
// table表示字符串t里的字符
if (s == null || s.length() == 0 || t == null || t.length() == 0)
return "";
int[] table = new int[128];
int count = t.length();
for (int i = 0; i < count; i++)
table[t.charAt(i)] += 1;
// l表示滑动窗口的左端,r表示滑动窗口的右端
int l = 0, r = 0, ans = Integer.MAX_VALUE, start = 0;
while (r < s.length()){
char c = s.charAt(r);
if (table[c] > 0) // 大于0表示t中的这个字符还没有取完
count--;
table[c]--;
// 当count等于0时,说明t中的字符已经全部包含在l-r这个区间。
// 因为题目求的是最小子串,所以这时候要向右移动l
if (count == 0){
// 当table[某个字符]小于0时,说明当前碰到的字符不是属于t中的。如果属于t中的,table的数值应该是0
while (l < r && table[s.charAt(l)] < 0){
table[s.charAt(l)]++;
l++;
}
if (r - l + 1 < ans){
ans = r - l + 1;
start = l;
}
table[s.charAt(l)]++;
l++;
count++;
}
r++;
}
return ans == Integer.MAX_VALUE? "": s.substring(start, start + ans);
}
}