LeetCode-30 串联所有单词的子串题解

设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;
    }
}

执行用时大大减少：

LeetCode-30 串联所有单词的子串题解

HHao

一条评论

留下评论取消回复