LeetCode 76.最小覆蓋子串

  • 題目詳情
  • 暴力解法與不足
  • 最優解：滑動窗口 + 哈希表
  • 核心思路
  • 代碼關鍵點解析
  • 哈希表的作用
  • 滑動窗口的收縮條件
  • 複雜度分析
  • 總結與擴展

題目詳情

LeetCode 76.最小覆蓋子串

暴力解法與不足

最直接的思路是枚舉 s 的所有子串，檢查每個子串是否包含 t 的所有字符，然後找出最短的那個。這種方法的時間複雜度為 O(n³)（枚舉子串 O(n²)，檢查包含關係 O(n)），在字符串較長時會嚴重超時。

最優解：滑動窗口 + 哈希表

核心思路

使用雙指針維護一個動態的窗口，通過擴展右指針來尋找可行解，然後收縮左指針來優化解，最終找到最短的滿足條件的子串。

算法步驟詳解

  1. 初始化哈希表
    使用哈希表記錄 t 中每個字符的出現次數
    使用另一個哈希表記錄當前窗口中字符的出現次數
  2. 滑動窗口過程
    右指針向右移動，擴展窗口，直到窗口包含 t 的所有字符
    當窗口滿足條件時，左指針向右移動，收縮窗口，尋找更優解
    在收縮過程中更新最短子串的起始位置和長度
class Solution {
    
    public String minWindow(String s, String t) {

        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        int l = 0;
        int r = -1;
        int len = Integer.MAX_VALUE;
        int ansL = -1;
        int ansR = -1;
        while (r < s.length()) {
            r++;
            if (r < s.length()) {
                sMap.put(s.charAt(r), sMap.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (mapContains(sMap, tMap) && l <= r) {
                if (r - l + 1 < len) {
                    ansL = l;
                    ansR = r + 1;
                    len = r - l + 1;
                }
                sMap.put(s.charAt(l), sMap.getOrDefault(s.charAt(l), 0) - 1);
                l++;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(ansL, ansR);
    }

    private Boolean mapContains(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {

        for (Map.Entry<Character, Integer> tEntry : tMap.entrySet()) {
            if (!sMap.containsKey(tEntry.getKey())) {
                return false;
            }
            if (sMap.get(tEntry.getKey()) < tEntry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

代碼關鍵點解析

哈希表的作用

  1. tMap：記錄 t 中每個字符應該出現的次數
  2. sMap：記錄當前窗口中各字符的實際出現次數

滑動窗口的收縮條件

  1. 僅在 sMap包含tMap 時收縮，確保窗口始終在可行解附近優化
  2. 收縮過程中持續檢查是否能得到更短的子串

複雜度分析

時間複雜度：O(|s| + |t|)，每個字符最多被左右指針各訪問一次

空間複雜度：O(|s| + |t|)，主要用於存儲哈希表

總結與擴展

LeetCode 76是一個經典的滑動窗口應用題，掌握它有助於解決一系列類似問題：

關鍵思想：通過雙指針動態維護可行解區間，避免重複計算

優化技巧：使用哈希錶快速判斷條件滿足情況，用輔助變量減少遍歷開銷

相關題目：LeetCode 3(無重複字符的最長子串)、LeetCode 438(找到字符串中所有字母異位詞)

理解並掌握這種滑動窗口+哈希表的組合模式，對於解決字符串處理相關問題具有重要價值。