LeetCode 0030 - Substring with Concatenation of All Words
# Hints
- 哈希 + 双指针扫描
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
You are given a string, , and a list of words, , that are all of the same length. Find all starting indices of in that is a concatenation of each word in exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
# 题意
给定一个长为 的字符串 ,给定 个长度均为 的字符串 ,求 的所有满足条件的子串的起点 ,要求子串由 中的每个单词不重叠地首尾相接而成。首尾相接的顺序是任意的,每个单词都恰好出现一次,不允许其他无关字符出现在子串中。在 中可能存在相同的字符串。
# 题解
因为字符串的长度相同,所以我们完全可以从哈希的角度去考虑,字符串的长度对答案毫无影响。我们不妨先只考虑 的情形,那么问题退化为:
- 给定一个长为 的数组,指定 种元素的出现次数,求该数组的所有满足条件的连续子序列,满足其中每个元素的出现次数符合预设指定值。
显然该问题具有单调性,双指针扫描解决即可,时间复杂度为 。
回到原问题中,我们只需以 为单位去处理即可。唯一的问题在于,字符串 并不是有和 相关的规律性的,我们需要枚举求解的起点 而不是简单地令 。因此总的时间复杂度为 。
# AC代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string> & words) {
// 特判
if (s.length() == 0 || words.empty()) {
return vector<int>();
}
// 初始化
unordered_map<string, int> ump;
for (auto word : words) {
ump[word] ++;
}
// 遍历起点
vector<int> res;
int n = s.length(), m = words.size(), len = words[0].length();
for (int i = 0; i < len; i ++) {
// 主循环
unordered_map<string, int> cnt;
int left = i, right = i - len;
int sum = 0;
while (right <= n - len) {
// 递进
right += len;
sum ++;
// 获取子串
string word = s.substr(right, len);
// 不合法的情况
if (ump.find(word) == ump.end()) {
cnt.clear();
left = right + len;
sum = 0;
continue;
}
// 递进
cnt[word] ++;
while (left < right && cnt[word] > ump[word]) {
cnt[s.substr(left, len)] --;
left += len;
sum --;
}
// 更新答案
if (sum == m) {
res.push_back(left);
}
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01