LeetCode 76 最小覆蓋字串
在本篇博客中，我們將探討LeetCode上的一道算法題目——“最小覆蓋子串”。這道題的主要目標是找到字符串s中包含字符串t中所有字符的最小子串。
問題描述
給定字符串s和t，要求在字符串s中找到一個最小的子串，使得這個子串包含了字符串t中所有的字符。如果不存在這樣的子串，返回空字符串""。
解題思路
要解決這個問題，我們可以使用滑動窗口的方法。滑動窗口是一種經典的算法思想，在處理子串、子數組等問題時非常有效。
具體地，我們可以按照以下步驟進行：
- 創建兩個哈希表，一個用于存儲字符串t中每個字符的出現次數，另一個用于存儲當前窗口中每個字符的出現次數。
- 使用兩個指針，j指向窗口的左邊界，i指向窗口的右邊界 j和i初始化為0。
- 遍歷字符串s，移動i。
- 縮小窗口，移動j，盡量減小窗口大小同時保證包含字符串t中所有字符。
- 在遍歷過程中，更新最小子串的起始位置和長度。
實現代碼
class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> map, _map;string result;// 將要查找的字符放入到哈希表中for (auto i : t) map[i]++;// j左 i右for (int i = 0, j = 0, count = 0; i < s.length(); i++) {// 如果_map中加入字符后數量沒有超過map，說明是一個有效字符if (++_map[s[i]] <= map[s[i]]) count++;// 縮小窗口while (_map[s[j]] > map[s[j]]) _map[s[j++]]--;// 當窗口包含了t中所有字符時，更新最小子串if (count == t.length()) {if (result.empty() || result.size() > i - j + 1)result = s.substr(j, i - j + 1);}}return result;}
};
復雜度分析
時間復雜度分析
- 遍歷字符串s： 算法的主要部分是對字符串s進行一次線性遍歷，因此時間復雜度為O(n)，其中n是字符串s的長度。
- 內部循環： 內部循環中包含了兩個指針的移動，它們的時間復雜度取決于指針的移動次數。在最壞情況下，每個指針都可能移動n次，因此內部循環的時間復雜度也是O(n)。
- 哈希表操作： 哈希表的操作在最壞情況下可以達到O(1)的時間復雜度，因此哈希表的操作不會對總體復雜度造成影響。
綜上所述，算法的時間復雜度為O(n)。
空間復雜度分析
- 哈希表的空間復雜度： 算法中使用了兩個哈希表，它們存儲的鍵值對數量不會超過字符串t的長度，因此哈希表的空間復雜度為O(|t|)，其中|t|是字符串t的長度。
- 額外空間： 除了哈希表之外，算法只使用了常數級別的額外空間，因此不會對總體空間復雜度造成影響。
綜上所述，算法的空間復雜度為O(|t|)。
總結
本文介紹了如何利用滑動窗口的思想解決LeetCode中的"最小覆蓋子串"問題。通過使用兩個哈希表記錄字符出現次數，以及通過移動左右指針來確定子串的位置，我們可以高效地找到問題的解決方案。滑動窗口是一種在處理子串問題時非常有用的算法思想，可以幫助我們解決各種相關的問題。
)
