class Solution {
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
int tLen = t.length();
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = -1;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
while (r < sLen) {
1. 不斷右滑
++r;
if (r < sLen && ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
while (check() && l <= r) {
2. 已經(jīng)覆蓋子串芹敌，則左邊界右滑，進行收縮
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
宕機中爆侣，不理解了
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {
Iterator iter = ori.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
復(fù)雜度分析
時間復(fù)雜度：最壞情況下左右指針對 s 的每個元素各遍歷一遍酸钦，哈希表中對 s 中的每個元素各插入侈净、刪除一次有序，對 t 中的元素各插入一次跛十。每次檢查是否可行會遍歷整個 t 的哈希表唐含，哈希表的大小與字符集的大小有關(guān)浅浮，設(shè)字符集大小為 C，則漸進時間復(fù)雜度為 O(C?∣s∣+∣t∣)捷枯。
空間復(fù)雜度：這里用了兩張哈希表作為輔助空間滚秩，每張哈希表最多不會存放超過字符集大小的鍵值對，我們設(shè)字符集大小為 C 淮捆，則漸進空間復(fù)雜度為 O(C)郁油。
76. 最小覆蓋子串--滑動窗口（可優(yōu)化）
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來蹬碧，“玉大人舱禽，你說我怎么就攤上這事《鞴粒” “怎么了誊稚？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長。 經(jīng)常有香客問我里伯，道長城瞎，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任疾瓮，我火速辦了婚禮脖镀，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘狼电。我一直安慰自己蜒灰，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布肩碟。 她就那樣靜靜地躺著强窖，像睡著了一般。 火紅的嫁衣襯著肌膚如雪腾务。 梳的紋絲不亂的頭發(fā)上毕骡，一...
- 文/蒼蘭香墨 我猛地睜開眼密末，長吁一口氣：“原來是場噩夢啊……” “哼握爷！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起严里，我...
- 正文 年R本政府宣布置蜀，位于F島的核電站，受9級特大地震影響割粮，放射性物質(zhì)發(fā)生泄漏盾碗。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一舀瓢、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧耗美，春花似錦京髓、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至蛇摸，卻和暖如春备图，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背赶袄。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 76.最小覆蓋子串： 給你一個字符串 s 村刨、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串撰茎。如果 s ...
- 904. 水果成籃[https://leetcode.cn/problems/fruit-into-baskets...
- 滑動窗口問題乾吻，比如3[http://www.reibang.com/p/fc9fa4946c0a]和567[ht...
- 76. 最小覆蓋子串 題目來源：https://leetcode-cn.com/problems/minimum-...
