Description
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).思路
- 这题做得我蛋疼。做的时候，一直考虑优化优化，提交的时候才发现，这有特么情况太多了，优化个屁啊，优化半天还是800多ms
- 自己的具体思路就不写了，贴个代码出来
- 网上搬一个大佬的代码吧。唉。
代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if (s.empty() || words.empty()) return res;
unordered_map<string, int> hashMap;
unordered_map<string, int> copyMap;
unordered_map<string, int> cmpMap;
int len = words[0].size(), sumLen = 0;
for (int i = 0; i < words.size(); ++i){
hashMap[words[i]]++;
cmpMap[words[i]] = 0;
sumLen += words[i].size();
}
copyMap = hashMap;
int i = 0, sum = 0;
string tmp;
int flag = 1, curLen = 0, start = 0;
while (i < s.size()){
sum = 0;
tmp = s.substr(i, len);
if (copyMap.find(tmp) == copyMap.end()){
start++;
flag++;
curLen = 0;
hashMap = copyMap;
i = start;
}
else{
if (cmpMap[tmp] == flag){
if (hashMap[tmp] == 0){
hashMap = copyMap;
start++;
curLen = 0;
++flag;
i = start;
}
else{
hashMap[tmp]--;
curLen += len;
i += len;
}
}
else{
cmpMap[tmp] = flag;
hashMap[tmp]--;
curLen += len;
i += len;
}
}
if (curLen == sumLen){
res.push_back(start);
start++;
curLen = 0;
flag++;
i = start;
hashMap = copyMap;
}
}
return res;
}
};- 分析一个大佬的代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if (s.empty() || words.empty() || s.size() < words[0].size()) return res;
//一个用来保存原始字典，一个用来辅助
unordered_map<string, int> hashMap;
unordered_map<string, int> cmpMap;
int num = words.size();
int len = words[0].size();
for (int i = 0; i < num; ++i){
hashMap[words[i]]++;
}
int count = 0, start = 0;
string tmp;
//不需要从 0 - s.size() , 一个一个的遍历过去，其实，只可能以0-len这些开头，这是个重点，可以推的
for (int i = 0; i < len; ++i){
count = 0;
//重置start 和 map
start = i;
cmpMap.clear();
//每一次比较一个单词，而不是一个字符一个字符的比
for (int j = i; j <= s.size() - len; j += len){
tmp = s.substr(j, len);
//在里面
if (hashMap.find(tmp) != hashMap.end()){
cmpMap[tmp]++;
//当前单词可能在结果里面
if (cmpMap[tmp] <= hashMap[tmp]) count++;
else{
//当前单词已经重复了
//从start 开始减，把前面加进来的都减出去
while (cmpMap[tmp] > hashMap[tmp]){
string strTemp = s.substr(start, len);
cmpMap[strTemp]--;
if (cmpMap[strTemp] < hashMap[strTemp])
count--;
start += len;
}
}
//保存结果
if (count == num){
res.push_back(start);
cmpMap[s.substr(start, len)]--;
start += len;
count--;
}
}
else{
//不在字典中，重新开始
cmpMap.clear();
start = j + len;
count = 0;
}
}
}
return res;
}
};- 大佬的代码学到了很多，但是现在确实是没时间展开分析了。。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
