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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<int> FindSubstring(string s, string[] words) {
6 if (words.Length == 0) return new List<int>();
7
8 Dictionary<string, int> wordCount = new Dictionary<string, int>();
9 foreach (string word in words) {
10 if (!wordCount.ContainsKey(word)) {
11 wordCount[word] = 0;
12 }
13 wordCount[word]++;
14 }
15
16 int wordLength = words[0].Length;
17 int subStringLength = wordLength * words.Length;
18 List<int> indices = new List<int>();
19
20 for (int i = 0; i <= s.Length - subStringLength; i++) {
21 Dictionary<string, int> seen = new Dictionary<string, int>();
22 int j = 0;
23 while (j < words.Length) {
24 int wordIndex = i + j * wordLength;
25 string sub = s.Substring(wordIndex, wordLength);
26 if (!wordCount.ContainsKey(sub)) break;
27 if (!seen.ContainsKey(sub)) seen[sub] = 0;
28 seen[sub]++;
29 if (seen[sub] > wordCount[sub]) break;
30 j++;
31 }
32 if (j == words.Length) indices.Add(i);
33 }
34 return indices;
35 }
36}C# utilizes Dictionary to hold word counts and compares each possible starting index in a similar sliding window style, using break logic to ensure validity checking.