You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9]
.
(order does not matter).
class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { const int wordLength = L[0].size(); const int length = L.size()*wordLength; const int n = S.size(); vector<int> res; unordered_map<string, int> map; for (int i = 0; i < L.size(); i++) { ++map[L[i]]; } for (int i = 0; i < n - length + 1; i++) { unordered_map<string, int> used(map); for (int j = i; j < i + length; j += wordLength) { auto pos = used.find(S.substr(j, wordLength)); if (pos == used.end() || pos->second == 0) { break; } if (--pos->second == 0) { used.erase(pos); } } if (used.size() == 0) { res.push_back(i); } } return res; } };