- 這一題與 567 類似,差別是將字元比較改成字串比較。
- 注意因為字串比較不一定是從 0 開始,所以還要多一個
for start in range(0, wordLen)
的迴圈來調整起始位置
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> cnt1, cnt2;
for (const auto& word : words) cnt1[word]++;
int wordLen = words[0].size();
int k = words.size();
vector<int> res;
if (s.size() < wordLen * k) return res;
for (int start = 0; start < wordLen; start++) {
cnt2.clear();
int valid = 0;
for (int i = start; i < k * wordLen; i += wordLen) {
string sin = s.substr(i, wordLen);
if (cnt1.count(sin) && ++cnt2[sin] == cnt1[sin]) valid++;
}
if (valid == cnt1.size()) res.push_back(start);
for (int i = start + k * wordLen; i < s.size(); i += wordLen) {
string sin = s.substr(i, wordLen);
if (cnt1.count(sin) && ++cnt2[sin] == cnt1[sin]) valid++;
string sout = s.substr(i-k*wordLen, wordLen);
if (cnt1.count(sout) && cnt2[sout]-- == cnt1[sout]) valid--;
if (valid == cnt1.size()) res.push_back(i-(k-1)*wordLen);
}
}
return res;
}
};