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.
1from collections import Counter
2
3def findSubstring(s: str, words: List[str]) -> List[int]:
4 if not s or not words:
5 return []
6 word_length = len(words[0])
7 word_count = len(words)
8 substring_length = word_length * word_count
9
10 word_map = Counter(words)
11 result = []
12
13 for i in range(len(s) - substring_length + 1):
14 seen_words = Counter()
15 for j in range(word_count):
16 word_start = i + j * word_length
17 word = s[word_start:word_start + word_length]
18 if word in word_map:
19 seen_words[word] += 1
20 if seen_words[word] > word_map[word]:
21 break
22 else:
23 break
24 if seen_words == word_map:
25 result.append(i)
26
27 return result
28Using Python's Counter from collections, this script creates a dictionary for word counts and matches it against each possible starting location by traversing employing a nested for-loop structure with controlled breaks.