给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd","cdabef", "cdefab","efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
const int len = words.size();
const int len1 = words[0].size();
int sublen = len*len1;
if(s.size() < sublen) return {};
for(auto& word:words){
mymap[word]++;
}
vector<unordered_map<string, int> > vu(len1);
for(int i = 0;i < len1;i++){
for(int j = i; j < i + sublen;j += len1){
string s_sub = s.substr(j,len1);
vu[i][s_sub]++;
}
if(vu[i] == mymap){
res.emplace_back(i);
}
}
// sliding window: 滑动窗口,每次移动 d 个位置
for(int i = len1;i + sublen <= s.size(); i++){
int r = i % len1;
string wa = s.substr(i - len1, len1), wb = s.substr(i + sublen - len1, len1);
if(--vu[r][wa] == 0) vu[r].erase(wa);
vu[r][wb]++;
if (vu[r] == mymap) {
res.emplace_back(i);
}
}
return res;
}
private:
unordered_map<string,int> mymap;
vector<int> res;
};
标签:子串,串联,int,30,单词,len1,sublen,words
From: https://www.cnblogs.com/lihaoxiang/p/17813158.html