76. 最小覆蓋子串：
給你一個(gè)字符串 s 、一個(gè)字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。
注意：
- 對(duì)于
t中重復(fù)字符，我們尋找的子字符串中該字符數(shù)量必須不少于t中該字符數(shù)量。 - 如果
s中存在這樣的子串，我們保證它是唯一的答案。
樣例 1：
輸入：
s = "ADOBECODEBANC", t = "ABC"
輸出：
"BANC"
解釋：
最小覆蓋子串 "BANC" 包含來自字符串 t 的 'A'、'B' 和 'C'。
樣例 2：
輸入：
s = "a", t = "a"
輸出：
"a"
解釋：
整個(gè)字符串 s 是最小覆蓋子串。
樣例 3：
輸入:
s = "a", t = "aa"
輸出:
""
解釋:
t 中兩個(gè)字符 'a' 均應(yīng)包含在 s 的子串中，
因此沒有符合條件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length- 1 <= m, n <= 105
-
s和t由英文字母組成
進(jìn)階：
你能設(shè)計(jì)一個(gè)在 o(m + n) 時(shí)間內(nèi)解決此問題的算法嗎？文章來源：http://www.zghlxwxcb.cn/news/detail-694988.html
分析：
- 面對(duì)這道算法題目，二當(dāng)家的再次陷入了沉思。
- 直接采用雙層循環(huán)暴力解決的話，時(shí)間復(fù)雜度會(huì)比較高，恐怕過不了用例，沒有去試。
- 題目并不要求字符的順序，只要求了每種字符的數(shù)量，那首先就想到要做計(jì)數(shù)。
- 接下來考慮如何降低時(shí)間復(fù)雜度，每次循環(huán)都從新匹配子串是低效的，要盡可能復(fù)用，滑動(dòng)窗口在這里非常合適，使用雙指針，先直接移動(dòng)右指針找到第一個(gè)滿足條件的子串，記下長度作為備選結(jié)果，接下來移動(dòng)左指針，當(dāng)不滿足覆蓋子串的條件時(shí)就繼續(xù)移動(dòng)右置針直到滿足覆蓋子串的條件，并比較子串的長度，取較小的子串長度作為備選結(jié)果，重復(fù)該操作，直到循環(huán)遍歷完畢。
- 如何高效判斷遍歷的子串已經(jīng)滿足覆蓋子串呢？字符計(jì)數(shù)這時(shí)候就要大展拳腳了，先在遍歷字符串
s之前，先對(duì)字符串t進(jìn)行一次遍歷，做初始化計(jì)數(shù)，記錄下每種字符的個(gè)數(shù)（題解中這里使用了減法，使用加法也是可以的，只是后面的加減法就要變），在遍歷s時(shí)，移動(dòng)右指針就是延長了覆蓋子串，同時(shí)修改計(jì)數(shù)，這里的加減法計(jì)算要和前面初始化的相反，判斷計(jì)數(shù)是否為0，如果變?yōu)?則表示，這種字符的個(gè)數(shù)已經(jīng)沒有差異了，但是我們需要覆蓋了t中的每一種字符，所以需要判斷26個(gè)字符的個(gè)數(shù)是不是都?jí)蛄?，如果都?jí)蛄耍褪菨M足了覆蓋子串，接下來就移動(dòng)左指針，同時(shí)修改計(jì)數(shù)，這里的加減計(jì)算要和右指針移動(dòng)的相反。 - 當(dāng)某個(gè)字符的計(jì)數(shù)變?yōu)?時(shí)，我們需要判斷
26種字符的字符個(gè)數(shù)是不是都滿足了，這里就需要26次循環(huán)，是否有更高效的辦法呢？我們可以額外增加一個(gè)變量記錄有差異的字符種類數(shù)（記錄有差異的字符數(shù)也是可以的，但是后面的邏輯會(huì)有一點(diǎn)區(qū)別，思想大致相同）， 初始化時(shí)順便初始化該變量，在遍歷匹配中，每當(dāng)有字符計(jì)數(shù)變?yōu)?，就修改這個(gè)變量，如果這個(gè)變量變?yōu)?則表示完全覆蓋，從而提高效率。 - 只看文字可能不便理解，建議對(duì)照著熟悉的語言的題解一起看，希望可以有助學(xué)習(xí)理解。
題解：
rust：
impl Solution {
pub fn min_window(s: String, t: String) -> String {
// 少于目標(biāo)字符串中數(shù)量的字符數(shù)量
let mut diff_char_count = 0;
// 字符計(jì)數(shù)器
let mut cnt = vec![0; 128];
// 初始化
t.as_bytes().iter().for_each(|&b| {
// 計(jì)數(shù)減少
cnt[b as usize] -= 1;
if cnt[b as usize] == -1 {
// 差異字符數(shù)增加
diff_char_count += 1;
}
});
// 覆蓋子串結(jié)果信息
let (mut ans_len, mut ans_l) = (usize::MAX, usize::MAX);
// 開始滑動(dòng)窗口
let s_len = s.len();
let (mut l, mut r) = (0, 0);
while r < s_len {
// 計(jì)數(shù)增加
cnt[s.as_bytes()[r] as usize] += 1;
// 向右移動(dòng)右邊界后，可能該字符數(shù)量沒有差異了
if cnt[s.as_bytes()[r] as usize] == 0 {
// 差異字符數(shù)減少
diff_char_count -= 1;
// 差異字符數(shù)減少后可能為0了
if diff_char_count == 0 {
// 向右滑動(dòng)左邊界，直到會(huì)有差異，取滿足要求的最小串
while cnt[s.as_bytes()[l] as usize] > 0 {
cnt[s.as_bytes()[l] as usize] -= 1;
l += 1;
}
// 更新結(jié)果
if r - l + 1 < ans_len {
ans_len = r - l + 1;
ans_l = l;
}
// 向右移動(dòng)左邊界，差異字符數(shù)增加
cnt[s.as_bytes()[l] as usize] -= 1;
l += 1;
diff_char_count += 1;
}
}
r += 1;
}
return if ans_l == usize::MAX {
"".to_string()
} else {
s[ans_l..ans_l + ans_len].to_string()
}
}
}
go：
func minWindow(s string, t string) string {
// 少于目標(biāo)字符串中數(shù)量的字符數(shù)量
diffCharCount := 0
// 字符計(jì)數(shù)器
cnt := make([]int, 128)
// 初始化
for _, c := range t {
// 計(jì)數(shù)減少
cnt[c]--
if cnt[c] == -1 {
// 差異字符數(shù)增加
diffCharCount++
}
}
// 覆蓋子串結(jié)果信息
ansLen, ansL := math.MaxInt32, -1
// 開始滑動(dòng)窗口
sLen := len(s)
l, r := 0, 0
for r < sLen {
// 計(jì)數(shù)增加
cnt[s[r]]++
// 向右移動(dòng)右邊界后，可能該字符數(shù)量沒有差異了
if cnt[s[r]] == 0 {
// 差異字符數(shù)減少
diffCharCount--
// 差異字符數(shù)減少后可能為0了
if diffCharCount == 0 {
// 向右滑動(dòng)左邊界，直到會(huì)有差異，取滿足要求的最小串
for cnt[s[l]] > 0 {
cnt[s[l]]--
l++
}
// 更新結(jié)果
if r-l+1 < ansLen {
ansLen = r - l + 1
ansL = l
}
// 向右移動(dòng)左邊界，差異字符數(shù)增加
cnt[s[l]]--
l++
diffCharCount++
}
}
r++
}
if ansL == -1 {
return ""
} else {
return s[ansL : ansL+ansLen]
}
}
c++：
class Solution {
public:
string minWindow(string s, string t) {
// 少于目標(biāo)字符串中數(shù)量的字符數(shù)量
int diffCharCount = 0;
// 字符計(jì)數(shù)器
int cnt[128];
memset(cnt, 0, sizeof(cnt));
// 初始化
const int tLen = t.length();
for (int i = 0; i < tLen; ++i) {
if (--cnt[t[i]] == -1) {
// 差異字符數(shù)增加
++diffCharCount;
}
}
// 覆蓋子串結(jié)果信息
int ansLen = INT_MAX, ansL = -1;
// 開始滑動(dòng)窗口
const int sLen = s.length();
int l = 0, r = -1;
while (++r < sLen) {
// 向右移動(dòng)右邊界后，可能該字符數(shù)量沒有差異了
if (++cnt[s[r]] == 0) {
// 差異字符數(shù)減少后可能為0了
if (--diffCharCount == 0) {
// 向右滑動(dòng)左邊界，直到會(huì)有差異，取滿足要求的最小串
while (--cnt[s[l++]] >= 0) {
// nothing
}
// 差異字符數(shù)增加
++diffCharCount;
// 更新結(jié)果
if (r - l + 2 < ansLen) {
ansLen = r - l + 2;
ansL = l - 1;
}
}
}
}
return ansL == -1 ? "" : s.substr(ansL, ansLen);
}
};
python：
class Solution:
def minWindow(self, s: str, t: str) -> str:
# 少于目標(biāo)字符串中數(shù)量的字符數(shù)量
diff_char_count = 0
# 字符計(jì)數(shù)器
cnt = collections.defaultdict(int)
# 初始化
for c in t:
# 計(jì)數(shù)減少
cnt[c] -= 1
if cnt[c] == -1:
# 差異字符數(shù)增加
diff_char_count += 1
# 覆蓋子串結(jié)果信息
ans_len, ans_l = float("inf"), -1
# 開始滑動(dòng)窗口
s_len = len(s)
l, r = 0, 0
while r < s_len:
# 計(jì)數(shù)增加
cnt[s[r]] += 1
# 向右移動(dòng)右邊界后，可能該字符數(shù)量沒有差異了
if cnt[s[r]] == 0:
# 差異字符數(shù)減少
diff_char_count -= 1
# 差異字符數(shù)減少后可能為0了
if diff_char_count == 0:
# 向右滑動(dòng)左邊界，直到會(huì)有差異，取滿足要求的最小串
while cnt[s[l]] > 0:
cnt[s[l]] -= 1
l += 1
# 更新結(jié)果
if r - l + 1 < ans_len:
ans_len = r - l + 1
ans_l = l
# 向右移動(dòng)左邊界，差異字符數(shù)增加
cnt[s[l]] -= 1
l += 1
diff_char_count += 1
r += 1
return "" if ans_l == -1 else s[ans_l: ans_l + ans_len]
java：
class Solution {
public String minWindow(String s, String t) {
// 少于目標(biāo)字符串中數(shù)量的字符數(shù)量
int diffCharCount = 0;
// 字符計(jì)數(shù)器
final int[] cnt = new int[128];
// 初始化
final int tLen = t.length();
for (int i = 0; i < tLen; ++i) {
if (--cnt[t.charAt(i)] == -1) {
// 差異字符數(shù)增加
++diffCharCount;
}
}
// 覆蓋子串結(jié)果信息
int ansLen = Integer.MAX_VALUE, ansL = -1;
// 開始滑動(dòng)窗口
final int sLen = s.length();
int l = 0, r = -1;
while (++r < sLen) {
// 向右移動(dòng)右邊界后，可能該字符數(shù)量沒有差異了
if (++cnt[s.charAt(r)] == 0) {
// 差異字符數(shù)減少后可能為0了
if (--diffCharCount == 0) {
// 向右滑動(dòng)左邊界，直到會(huì)有差異，取滿足要求的最小串
while (--cnt[s.charAt(l++)] >= 0) {
// nothing
}
// 差異字符數(shù)增加
++diffCharCount;
// 更新結(jié)果
if (r - l + 2 < ansLen) {
ansLen = r - l + 2;
ansL = l - 1;
}
}
}
}
return ansL == -1 ? "" : s.substring(ansL, ansL + ansLen);
}
}
非常感謝你閱讀本文~
歡迎【點(diǎn)贊】【收藏】【評(píng)論】三連走一波~
放棄不難，但堅(jiān)持一定很酷~
希望我們大家都能每天進(jìn)步一點(diǎn)點(diǎn)~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-694988.html
到了這里，關(guān)于算法leetcode｜76. 最小覆蓋子串（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
