Leetcode.76.Minimum Window Subst

题目

给定两个字符串, 求第一个字符串包含第二个字符串字符的最小子字符串.

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Input: S = "AD", T = "X"
Output: ""

思路

求一个子字符串, 需要设立left和right指针.
第二个字符串的字符可能有重复的, 需要设立一个map计算字符出现次数.

left = 0, right = 0.
固定left, 移动right, 先找出一个符合条件的字符串.
然后固定right, 移动left, 缩小窗口, 缩小后移动right.

string minWindow(string s, string t) {
    map<char,int> tMap;
    for(int i = 0;i < t.size();i++){
        tMap[t[i]]++;
    }

    int l = 0, r = 0;
    int pos = 0, len = 0;
    int count = (int)t.size();

    while (r < s.size()) {
        tMap[s[r]]--;
        if(tMap[s[r]] >= 0) count--;

        while (count == 0 && l <= r) {
            if (len == 0 || len > r - l + 1) {
                len = r -l + 1;
                pos = l;
            }
            if (++tMap[s[l++]] > 0) {
                count++;
            }
        }
        r++;
    }

    return s.substr(pos, len);
}

总结

理解流程, 固定一端移动另一端, 确定好固定项和