题目描述
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
样例
示例1:
输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例2:
输入:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出:[]
算法
一种比较简单的暴力做法是枚举s
的每个位置,然后考虑以该位置为起点是否存在一个由words
里所有单词拼接而成的字符串,由于每个word
长度相同,可以利用哈希表,一个单词一个单词的来枚举,看最后是否用完了words
里的单词并且中间不存在不合法的单词。这样的复杂度为$O(n * w * m)$,n
为字符串s
的长度,w
是单词的长度,m
是单词列表words
的长度。不过这个做法会超时。
下面我们考虑怎么优化这个做法,因为有单词长度都相同这个限制,问题可以转化成将字符串s
切成每段长度为w
的序列,那么不同的序列最多有多少个(长度不足w
的抛弃)?答案是w
个,从起点0,1,2,...,w-1
开始最多可以有w
个不同的单词序列,从w
开始的序列和从0
开始的是等价的。
所以我们就可以枚举每个序列,对于每个序列我们可以用双指针来搜索包含words
所有单词的连续序列。这里是以单词为单位进行双指针移动,双指针的思路类似于LeetCode 3. Longest Substring Without Repeating Characters , 我们每次将窗口右端的单词加入哈希表,如果它的个数大于words
中的个数,当前序列肯定不合法,我们不断地移动左端点使得窗口再次合法,当窗口长度为m
时说明我们找到了一个答案。
共有w
个序列,每次枚举序列需要$O(n)$的复杂度,总时间复杂度为$O(n * w)$,比暴力做法优化掉了单词列表长度$m$。
C++ 代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (words.empty()) return vector<int>();
unordered_map<string, int> hash;
for (auto &word : words) hash[word] ++ ;
vector<int> res;
int w = words[0].size(), n = words.size();
for (int i = 0; i < w; i ++ ) {
// 将序列切出来
vector<string> ws;
int j = i;
while (j + w - 1 < s.size()) {
ws.push_back(s.substr(j, w));
j += w;
}
// 双指针匹配
unordered_map<string, int> h;
for (int a = 0, b = 0; b < ws.size(); b ++ ) {
h[ws[b]] ++ ;
while (h[ws[b]] > hash[ws[b]]) {
h[ws[a]] -- ;
a ++ ;
}
// 这里下标应为第i个序列的第a个单词
if (b - a + 1 == n) res.push_back(i + a * w);
}
}
return res;
}
};