题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给两个字符串 s 和 t，求 s 中能够涵盖 t 的最小子字符串的长度。

思路分享

  1. 对于 ASCII 表专用的哈希表形式，直接用长 128 的数组比较省心省力，用专门设定长度有可能恰好忘记考虑边缘值；

  2. substr 方法的本质是拷贝一个字符串，所以执行效率低；

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool isCover(int *recs, int *rect) {
        for (int i = 'a'; i <= 'z'; i++) {
            if (recs[i] < rect[i]) return false;
        }
        for (int i = 'A'; i <= 'Z'; i++) {
            if (recs[i] < rect[i]) return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        string ans = "";
        int rect['z'+1]{};
        int recs['z'+1]{};
        for (const char &c : t) {
            rect[c]++;
        }
        int left = 0;
        int ans_left = -1, ans_right = s.size();
        for (int right = 0; right < s.size(); right++) {
            recs[s[right]]++;
            while(isCover(recs, rect)) {
                if ((ans_right-ans_left)>(right-left)) {
                    ans_left = left;
                    ans_right = right;
                }
                //cout << ans << endl;
                recs[s[left]]--;
                left++;
            }
        }
        return ans_left==-1?"":s.substr(ans_left, ans_right-ans_left+1);
    }
};