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 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []
AC code:
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> mario;
vector<int> res={};
int len1 = s.length(), num = words.size();
if (len1 == 0 || num == 0) return res;
int len2 = words[0].length();
for (int i = 0; i < words.size(); ++i) {
mario[words[i]]++;
}
for (int i = 0; i < len1-num*len2+1; ++i) {
unordered_map<string, int> seen;
int j = 0;
for (; j < num; ++j) {
string word = s.substr(i+j*len2, len2);
if (mario.find(word) != mario.end()) {
seen[word]++;
if (seen[word] > mario[word])
break;
} else
break;
}
if (j == num)
res.push_back(i);
}
return res;
}
};
Runtime: 132 ms, faster than 49.73% of C++ online submissions for Substring with Concatenation of All Words.