22.02.27 学习
算法1
(暴力做法) $O(nw)$
过程:哈希表+双指针
1. w
为p
串包含的单词数,即s
串有w
种划分的匹配方法
2. 开两个哈希表。一个存p串中所有单词出现的次数tot
,一个记录滑动窗口中的单词出现次数wd
3. 构建滑动窗口,以及有效单词数cnt。滑动判断比较知否达到匹配条件cnt==m
4. 滑出与滑入对word
进行哈希判定,看好注释中的判断条件即可
时间复杂度分析
- 划分匹配种类为$O(w)$方法,一种匹配中,每一窗口
(p串)
一共插入弹出匹配完整个s串
是$O(n/w)$,每一次插入弹出都是$O(1)$,但是插入的是一个单词长度为w
,综上总的时间复杂度是 $O(w * n / w * w) = O(nw)$
C++代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if (words.empty()) return res;
int n = s.size(), m = words.size(), w = words[0].size();
unordered_map<string, int> tot; // 单词出现总数的哈希表tot
for (auto word : words) tot[word] ++ ; // 统计words中,所有单词出现的次数
for (int i = 0; i < w; i ++ ) { // s串可以有w种划分方法,即w种遍历匹配
unordered_map<string, int> wd; // 维护滑动窗口的哈希表wd
int cnt = 0; // cnt:窗口中有效单词的数量 --- 判断是否达到匹配
for (int j = i; j <= n - w; j += w) { // 构建滑动窗口,j指针匹配窗口内单词,每次跳w距离
// 滑出窗口
if (j >= i + m * w) {
auto word = s.substr(j - m * w, w); // 拿到窗口的第一个单词
wd[word] -- ; // 弹出word,wd哈希表中word数量-1
if (wd[word] < tot[word]) cnt -- ; // 如果wd中的word次数<tot中的word次数,说明找到了一个合法单词,cnt--
}
// 滑入窗口
auto word = s.substr(j, w); // 拿到窗口的下一个单词word
wd[word] ++ ; // wd哈希表中word数量+1
if (wd[word] <= tot[word]) cnt ++ ; //合法字符,cnt++;如果大于,就是找到了words串中没有的单词
if (cnt == m) res.push_back(j - (m - 1) * w); // 所有单词都匹配到,找到一个答案
}
}
return res;
}
};