刷题76. Minimum Window Substring

标签：ssi   自动   size   思路   字符   创建   mat   start   赋值   

一、题目说明

题目76. Minimum Window Substring，求字符串S中最小连续字符串，包括字符串T中的所有字符，复杂度要求是O(n)。难度是Hard！

二、我的解答

先说我的思路：

（1）统计t中每个字符出现的次数，

（2）用hash存储s中出现t中字符的位置，

（3）计算最短字符串。

思路有了，惭愧的是，这个题目，我没做出来。

后来参考大神的实现了，用“滑动窗口”实现。

代码如下：

class Solution{
    public:
        string minWindow(string s,string t){
            if(s.empty() || t.empty()) return "";
            int left=0,right=0;
            string res = s;
            int minLen = INT_MAX;
            int start = 0;

            unordered_map window;//当前「窗口」中包含的字符及出现的次数
            unordered_map needs;//t 中包含的字符及出现次数
            
            
            //统计字符串t中各个字符的数量
            for(char ch:t){
                needs[ch]++;//如果该 key不存在，C++ 会自动创建这个 key，并把 map[key] 赋值为 0
            }
            
            int match = 0;//记录 window 中已经有多少字符符合要求了
            
            while(right

性能一般：

Runtime: 28 ms, faster than 45.63% of C++ online submissions for Minimum Window Substring.
Memory Usage: 10.2 MB, less than 68.00% of C++ online submissions for Minimum Window Substring.

三、优化措施

我消化消化再说。

刷题76. Minimum Window Substring

标签：ssi   自动   size   思路   字符   创建   mat   start   赋值   

原文地址：https://www.cnblogs.com/siweihz/p/12252807.html