溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“leetcode如何實現最小覆蓋子串”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“leetcode如何實現最小覆蓋子串”這篇文章吧。
給定一個字符串 S 和一個字符串 T，請在 S 中找出包含 T 所有字母的最小子串。
示例：
輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"說明：
如果 S 中不存這樣的子串，則返回空字符串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。
解題思路：
1，用hashmap存儲s和t中字符出現的次數
2，移動右指針，對于s中的每個字符，如果出現在t中，且s中出現的次數不大于t中出現的次數，說明我們找到了一個匹配字符，記錄下來fund
3，如果found和t的長度相同，說明找到了解
A，包含t中所有字符
B，包含了部分重復字符（沒有記錄到fund中），說明，有些字符在s中出現的頻率大于t中出現的頻率
4，如果左指針對應字符在s中頻率大于t中的頻率，則應該舍棄這個字符，即移動左指針，調整對應次數
5，如果次數和t中相等，說明我們找到了一個局部最優解，記錄下來
6，右移左指針，并且減少fund，尋找下一個局部最優解。
func minWindow(s string, t string) string { src:=make(map[byte]int) dst:=make(map[byte]int) for i:=0;i<len(t);i++{ dst[t[i]]++ } start:=0 found:=0 min:=len(s) begin:=-1 for end:=0;end<len(s);end++{ src[s[end]]++ if src[s[end]]<=dst[s[end]]{ found++ } if found==len(t){ for start<end && src[s[start]]>dst[s[start]]{ src[s[start]]-- start++ } if end-start<min{ min=end-start begin=start } src[s[start]]-- start++ found-- } } if begin==-1{ return "" } return string(s[begin:begin+min+1])}
以上是“leetcode如何實現最小覆蓋子串”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
