设wordLength为单词长度,wordCount为单词数量。
看到了这题的标签滑动窗口,就想到了最朴素的方法。设windowSize = wordCount * wordLength,从头至尾移动窗口,检查窗口内的子串是否符合要求。
检查窗口内子串是否符合要求的做法是,使用Hash表,以单词为key,出现次数为value。例如第2个窗口“ordgoodgoodgoodb”,包含的单词为“ordg oodg oodg oodb”,对应表为“ordg:1, oodg:2, oodb:1”。同理把给定的words转换为Hash表,对比这两个表是否一致,一致则说明符合要求。代码如下:
public class Solution { public IList<int> FindSubstring(string s, string[] words) { int wordLength = words[0].Length; int wordCount = words.Length; int windowSize = wordCount * wordLength; if (s.Length < windowSize) { return []; } Dictionary<string, int> map = new(); foreach (string word in words) { if (!map.TryAdd(word, 1)) { map[word] += 1; } } List<int> result = []; for (int i = 0; i < s.Length - windowSize + 1; i++) { bool isValid = true; Dictionary<string, int> tempMap = new(map); for (int j = 0; j < wordCount; j++) { string fragment = s[(i + j * wordLength)..(i + j * wordLength + wordLength)]; if (!tempMap.ContainsKey(fragment) || tempMap[fragment] == 0) { isValid = false; break; } tempMap[fragment] -= 1; } if (isValid) { result.Add(i); } } return result; } }
但是时间复杂度太高了,虽然能过,但执行时间还是太长:
看了好多题解,都不是很明白,后来结合着想了想,优化了一下思路。上述解法是把滑动窗口瞄准了原始字符串,每次滑动只移动一个字符,但其实我们要判断的一个个的单词,移动一次窗口前后两个窗口之间并没有什么关联性,因此很难优化。若我们能每次窗口移动的是一个单词就好了,这样每次窗口移出去的是一个单词,新加入的也是一个单词,前后之间有重叠的部分,这样我们就可以进行优化了。
但是要怎么样确保移入移出的是一个单词呢?这里每个单词长度都是固定的,所以若考虑第1到wordLength个字符为一个单词、第wordLength+1到2*wordLength个字符为一个单词,依次类推,以上为一组划分;第2到wordLength+1个字符为一个单词、第wordLength+2到3*wordLength个字符为一个单词,依次类推,以上为一组划分……依次类推,一共可以分出wordLength组,如下图所示,每一行为一组划分:
这样一来,我们对每一组内的单词做滑动窗口,此时windowSize即为wordCount,接着逐一判断每个窗口是否符合要求即可。而此时,就不需要每个窗口重新创建一个新的Hash表了,只需要沿用上一个窗口的表,将已经移除出去的单词从统计表里减一、新加入的单词加入统计表里即可。代码如下:
public class Solution { public IList<int> FindSubstring(string s, string[] words) { int wordLength = words[0].Length; int wordCount = words.Length; if (s.Length < wordCount * wordLength) { return []; } Dictionary<string, int> map = new(); foreach (string word in words) { if (!map.TryAdd(word, 1)) { map[word] += 1; } } List<int> result = []; for (int i = 0; i < wordLength; i++) { int k = 0; Dictionary<string, int> tempMap = new(wordCount); for (int j = 0; j < s.Length / wordLength; j++) { if (i + j * wordLength + wordLength > s.Length) { continue; } string fragment = s.Substring(i + j * wordLength, wordLength); if (!tempMap.TryAdd(fragment, 1)) { tempMap[fragment]++; } k++; if (k == wordCount + 1) { k--; string head = s.Substring(i + j * wordLength - k * wordLength, wordLength); tempMap[head]--; if (tempMap[head] == 0) { tempMap.Remove(head); } } if (k == wordCount) { bool isValid = true; foreach (string key in map.Keys) { if (!tempMap.ContainsKey(key) || map[key] != tempMap[key]) { isValid = false; break; } } if (isValid) { result.Add(i + (j - k + 1) * wordLength); } } } } return result; } }
执行用时大大减少:
这篇文章写得深入浅出,让我这个小白也看懂了!