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;
}
};
- 大佬的代碼學到了很多,但是現在确實是沒時間展開分析了。。
轉載于:https://www.cnblogs.com/lengender-12/p/6832666.html