Sponsored
Sponsored
This approach uses a sliding window to find matching substrings. We utilize two hashmaps: one for the word list to track required counts of each word, and another to track what an occurring window currently constitutes.
The window slides over the string s while maintaining a fixed size (product of total words and word length). Each time the end of the window is extended, we evaluate if the slice of the string corresponds to a valid word by checking in the hashmap.
Time complexity: O(n * m * k) where n is the length of the string, m is the length of each word, and k is the number of words.
Space complexity: O(m) for the dictionaries holding word counts.
1#include <unordered_map>
2#include <vector>
3using namespace std;
4
5vector<int> findSubstring(string s, vector<string>& words) {
6 if(words.empty()) return {};
7
8 unordered_map<string, int> wordMap;
9 unordered_map<string, int> windowMap;
10
11 int wordLen = words[0].size();
12 int wordCount = words.size();
13 int subLen = wordLen * wordCount;
14 vector<int> result;
15
16 for (auto &word : words) wordMap[word]++;
17
18 for (int i = 0; i <= s.size() - subLen; i++) {
19 windowMap.clear();
20 int j = 0;
21 for (; j < wordCount; j++) {
22 int wordBegin = i + j * wordLen;
23 string word = s.substr(wordBegin, wordLen);
24 if (wordMap.find(word) == wordMap.end()) break;
25 windowMap[word]++;
26 if (windowMap[word] > wordMap[word]) break;
27 }
28 if (j == wordCount) result.push_back(i);
29 }
30 return result;
31}
32The C++ code uses unordered maps to track counts of words and an ongoing window check which extends through each relevant substring in s.