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.
1function findSubstring(s, words) {
2 if (!words || words.length === 0) return [];
3
4 let wordLength = words[0].length;
5 let wordCount = words.length;
6 let allWordsLength = wordLength * wordCount;
7 let result = [];
8 let wordMap = {};
9
10 // Fill wordMap
11 for (let word of words) {
12 wordMap[word] = (wordMap[word] || 0) + 1;
13 }
14
15 for (let i = 0; i <= s.length - allWordsLength; i++) {
16 let seenWords = {};
17 let j = 0;
18 for (; j < wordCount; j++) {
19 let wordStartIndex = i + j * wordLength;
20 let word = s.substring(wordStartIndex, wordStartIndex + wordLength);
21 if (!wordMap[word]) break;
22 seenWords[word] = (seenWords[word] || 0) + 1;
23 if (seenWords[word] > wordMap[word]) break;
24 }
25 if (j === wordCount) result.push(i);
26 }
27
28 return result;
29}JavaScript applies regular objects as hashmaps to store word counts. It uses nested loops with break control to ascertain if words in a slice are correctly mapped to the original list.