覆蓋最小子串
- 代碼來自b站左程云
class Solution {public String minWindow(String str, String tar) {char[] s = str.toCharArray();char[] t = tar.toCharArray();int[] cnt = new int[256];for (char cha : t) { cnt[cha]--;}int len = Integer.MAX_VALUE;int debt = t.length;int start = 0;for (int r = 0, l = 0; r < s.length; r ++) { if (cnt[s[r]]++ < 0) { debt--;}if (debt == 0) { while (cnt[s[l]] > 0) { cnt[s[l++]]--;}if (r - l + 1 < len) { len = r - l + 1;start = l;}}}return len == Integer.MAX_VALUE ? "" : str.substring(start, start + len);}
}
畫圖理解題意
- 我們先梳理一下思路：
- 我們要確定這個窗口有沒有包含target字符串中的每一個字符，難道我們要遍歷比較嗎？顯然不行，那么怎么樣讓它遍歷一次就知道是否包含呢？
- 我們利用之前前綴和中哈希表的思路，我們把target字符串的每個字符出現的次數作為每個字符欠債的個數存到數組中，把它弄成一個前債表。
- 我們看第一個樣例：
初始的欠債表為：
說明此時我們要找到一個滿足ABC每個字符各一個的組合。
當我們不斷擴展右邊界，會發現第一次滿足條件的窗口是這樣的：
可是題目要我們求最短啊，我們嘗試收縮左邊界，收縮的時候要注意，如果收縮會導致欠債那么就不能收縮，只能記住答案，拿去與之前比大小看是否能更新。
然后繼續擴展右邊界：
此時我們發現，不僅不欠債還有了結余可以嘗試收縮。
繼續這樣推下去，就是不斷進行這個判斷過程：
理解代碼：
if (cnt[s[r]]++ < 0) { debt--;}
這里是把每一個字符扔到欠債表里面進行結算，如果是target里面的，說明他剛開始是負的，所以我們用是否小于0來判斷是否可以對欠債總數debt來進行削減，到0的時候就說明我們要開始嘗試收縮窗口了。
if (debt == 0) { while (cnt[s[l]] > 0) { cnt[s[l++]]--;}if (r - l + 1 < len) { len = r - l + 1;start = l;}}
要判斷左邊是否可以削減，就要看它的削減會不會導致債務的增加，也就是會不會導致現在的窗口不能完全包含target，所以進行此判斷。
然后我們就要看這個窗口長度是不是目前最短的，是的話就更新它，同時記住此時左邊界，為什么？因為我們要返回的是一個字符串，截取一個子串需要它的長度和起始位置。
)
