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.
1int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
2 int wordLen = strlen(words[0]);
3 int allWordsLen = wordLen * wordsSize;
4 int strLen = strlen(s);
5 int *indices = (int *)malloc(sizeof(int) * strLen);
6 *returnSize = 0;
7
8 // Corner cases check
9 if (wordsSize == 0 || strLen < allWordsLen) return indices;
10
11 // Initialize word count
12 int wordCount[5000][26] = {0}; // assumption based index
13 int neededCount[26] = {0}, scar = 0;
14
15 for (int i = 0; i < wordsSize; i++) {
16 for (int j = 0; j < wordLen; j++) {
17 int wInd = words[i][j] - 'a';
18 if (wordCount[i][wInd] == 0) neededCount[wInd]++;
19 wordCount[i][wInd] = 1;
20 }
21 }
22
23 for (int i = 0; i <= strLen - allWordsLen; i++) {
24 int usedWords[26] = {0};
25 int j;
26 for (j = 0; j < allWordsLen; j += wordLen) {
27 int wIndex = s[i+j] - 'a';
28 if (++usedWords[wIndex] > neededCount[wIndex]) break;
29 }
30
31 if (j == allWordsLen) indices[(*returnSize)++] = i;
32 }
33
34 return indices;
35}
36The C code uses arrays to count the appearance of each letter in words, and then evaluates at each position if a segment of the string matches a permutation of the words.