【C++习题】15.滑动窗口_串联所有单词的子串

---

题目链接：

30. 串联所有单词的子串

---

题目描述：

---

解法

滑动窗口+哈希表

这题和第14题不同的是：

1. 哈希表不同：hash<string,int>
2. left与right指针的移动不同：移动的步长是每个单词的长度
3. 滑动窗口执行的次数不同

---

C++ 算法代码：

class Solution 
{
    public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> ret;
        unordered_map<string, int> hash1; // hash1保存 words 里面所有单词的频次
        for(auto& s : words) hash1[s]++; //统计 word 出现的次数
        int len = words[0].size(), m = words.size(); //len 表示每个单词的长度，m 表示单词的总数
        for(int i = 0; i < len; i++) // 执行 len 次
        {
            unordered_map<string, int> hash2; // 维护窗口内单词的频次
            for(int left = i, right = i, count = 0; right + len <= s.size(); 
                right += len)
            {
                // 进窗口 + 维护 count
                string in = s.substr(right, len);//从字符串 s 中提取一个长度为 len 的子串
                //s.substr(right, len) 这是一个字符串函数，用于从字符串 s 中提取子串。
//right 是当前窗口的起始位置。
//len 是每个单词的长度。
                hash2[in]++;//并将其存储在 hash2 中，用于统计当前滑动窗口内单词的出现次数
                /*
                hash1 是一个 unordered_map，用于存储 words 列表中每个单词的出现频次。
hash1.count(in) 检查单词 in 是否存在于 hash1 中。
如果 in 存在于 hash1 中，hash1.count(in) 返回 1（真）。
如果 in 不存在于 hash1 中，hash1.count(in) 返回 0（假）。
hash2[in] <= hash1[in]
这部分代码检查当前单词 in 在 hash2 中的出现次数是否小于或等于它在 words 列表中的出现次数（即 hash1[in]）。
如果 hash2[in] 小于或等于 hash1[in]，说明当前窗口内单词 in 的出现次数没有超过 words 列表中的限制。
*/
                if(hash1.count(in) && hash2[in] <= hash1[in]) 
                {
                    count++;
                }
                // 判断
                if(right - left + 1 > len * m)
                {
                    // 出窗口 + 维护 count
                    string out = s.substr(left, len); //s.substr(left, len) ，这个子串 out 是当前窗口最左边的单词。
                    /*
                    hash1.count(out) 检查 out 是否存在于 hash1 中
                    hash2[out] <= hash1[out] 检查当前窗口内 out 的出现次数是否小于或等于 words 列表中 out 的出现次数。
                    如果这两个条件都满足，说明 out 是一个有效的单词，当前窗口的有效单词计数 count 需要减少 1。
                    */
                    if(hash1.count(out) && hash2[out] <= hash1[out]) 
                    {
                        count--;
                    }
                    hash2[out]--; //更新 hash2 中 out 的计数:hash2[out]-- 将 out 在 hash2 中的计数减 1，因为 out 已经离开当前窗口
                    left += len;//left += len 将窗口的左边界向右移动 len 个位置，准备进行下一步的窗口滑动
                }
                // 更新结果
                if(count == m) 
                {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};

---

图解

例如：s = "barfoothefoobarman", words = ["foo","bar"]

1. hash1[foo]=1，hash1[bar]=1

   len=3，m=2

   in=bar，hash2[bar]++后=1

   满足if(hash1.count(in) && hash2[in] <= hash1[in]) ，count++

   right += len

2. in=foo，hash2[foo]++后=1

   满足if(hash1.count(in) && hash2[in] <= hash1[in]) ，count++

   满足if(count == m) ，所以ret.push_back(left);也就是0

   right += len

3. in=the，hash2[the]++后=1

   right += len

4. in=foo，hash2[foo]++后=2

   满足if(right - left + 1 > len * m)，out=bar，out不是有效字符，count不会减少，hash2[out]--;left += len;

   right += len

5. 后面步骤类似，就不多赘述了

原文地址：https://blog.csdn.net/hlyd520/article/details/144095555

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！