力扣(LeetCode)30. 串联所有单词的子串(C++)

滑动窗口+哈希表

哈希表 $tot$ 存 $words$ 所有单词的出现次数。

维护滑动窗口，窗口长度 $m\times w$ ， $m$ 是单词数量 $w$是单词长度 ， 窗口长度对应可行解的长度。哈希表 $wd$ 维护滑动窗口内每个单词的出现次数。

维护有效串总数 $cnt$ ，当 $cnt=m$ 时，找到一个可行解。当右窗口右移，加入的单词是需要的，$cnt++$ ， 当左窗口右移，移除的单词是需要的，$cnt--$ 。 对照 $wd$ 和 $tot$ 判断单词是否需要 。

提示 ： 滑动窗口达到最大长度后，维护左窗口。

将 $s$ 分成 $w$ 组，起点从 $0$ 到 $w-1$ ，遍历每一组，得到答案。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {//字符串哈希
        vector<int> ans;
        if(words.empty()) return ans;
        unordered_map<string,int> tot;
        for(auto &x:words) tot[x]++;
        int n = s.size(),m = words.size(),w = words[0].size();
        for(int i = 0;i<w;i++){
            int cnt = 0;
            unordered_map<string,int> wd;
            for(int j = i ;j<=n;j+=w){
                if(j >= i + m*w){//滑动窗口满了，维护左窗口
                    auto s1 = s.substr(j-m*w,w);
                    wd[s1]--;
                    if(tot[s1]>wd[s1]) cnt--;//减去了有效串
                }
                auto s2 = s.substr(j,w);
                wd[s2]++;
                if(tot[s2]>=wd[s2]) cnt++;//增加了有效串
                if(m == cnt) ans.push_back(j-(m-1)*w);
            }
        }
        return ans;
    }
};
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

1. 时间复杂度 : $O(w\times n)$ ， $n$ 是字符串 $s$ 的长度， $w$ 是单词长度。遍历 $w$ 组的时间复杂度 $O(w)$ ，每组 $\frac{n}{w}$ 个单词的时间复杂度 $O(\frac{n}{w})$ ，遍历字母得到单词的时间复杂度 $O(w)$ ，三者是相乘关系，总时间复杂度 $O(w\times n)$。
2. 空间复杂度 : $O(w\times m)$ ， $m$ 是单词总数 $words$ 的长度 ， $w$ 是单词长度。 哈希表 $tot$ 的空间复杂度是 $O(w\times m)$ ， 哈希表 $tot$ 的空间复杂度是 $O(w\times m)$ ，总空间复杂度是 $O(2\times w\times m)$ 。 忽略常数空间复杂度 $O(w\times m)$ 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC