[LeetCode]Substring with Concatenation of All Words

所有words都是等长度并且unique的，所以我们不需要考虑一个string是另一个的prefix的情况。例如abcab，words=["ab", "abc"]，显然我们应该每次尽量match到最长，如果我们只match ab那么我们得不到结果。这一题的条件帮我们排除了这种可能，本质上就类似于给定一系列的char看string是否有由这些char组成的substring。我们用sliding window动态地维护左右边界即可。碰到不match的直接跳过，match的加入，如果发现当前string的数量超过words里数量了，就移动左边界直到满足条件。假设input string长度n，每个word的长度为d，我们每次遍历的时间是n / d。我们要分别以[0, d - 1]开头遍历d次，总的时间复杂度就是n / d * d = O(n)。空间复杂度O(n)，代码如下：