LeetCode串联单词子串：滑动窗口与哈希统计解法-拓冰建站

1. 问题解析：理解串联所有单词的子串

这道LeetCode Hard题目要求我们找到字符串中所有可以由给定单词列表任意排列串联形成的子串起始位置。举个例子，如果字符串是"barfoothefoobarman"，单词列表是["foo", "bar"]，那么我们需要返回[0,9]，因为在位置0开始的子串"barfoo"和位置9开始的子串"foobar"都是由这两个单词排列组合形成的。

1.1 核心难点剖析

这个问题的复杂性主要体现在三个方面：

单词需要全排列组合：不像简单的子串匹配，这里需要考虑单词的各种排列可能性
单词长度固定但顺序不定：所有单词长度相同，但出现的顺序可能是任意的
可能存在重复单词：单词列表中可能有重复元素，需要准确计数

我最初尝试暴力解法时，发现当单词数量较多时，排列组合的数量会呈阶乘级增长，导致算法效率极低。比如有5个单词时，排列组合就有120种可能，这在算法设计中是不可接受的。

1.2 关键观察点

经过多次尝试和优化，我发现以下几个关键观察点可以大幅提升算法效率：

所有单词长度相同，这意味着我们可以按固定长度窗口滑动
不需要真正生成所有排列组合，只需要统计单词出现频率是否匹配
可以分批次检查，避免重复计算

2. 高效解法设计与实现

2.1 滑动窗口+哈希统计法

最优解法采用滑动窗口配合哈希统计，时间复杂度可以优化到O(n*m)，其中n是字符串长度，m是单词长度。以下是具体实现步骤：

from collections import defaultdict def findSubstring(s, words): if not s or not words: return [] word_len = len(words[0]) total_len = word_len * len(words) word_count = defaultdict(int) for word in words: word_count[word] += 1 result = [] for i in range(len(s) - total_len + 1): seen = defaultdict(int) j = 0 while j < len(words): word = s[i + j * word_len : i + (j + 1) * word_len] if word in word_count: seen[word] += 1 if seen[word] > word_count[word]: break else: break j += 1 if j == len(words): result.append(i) return result

2.2 多起点滑动窗口优化

上述基础解法还可以进一步优化。考虑到单词长度固定，我们可以从不同的起始位置(0到word_len-1)分别滑动窗口，这样可以避免遗漏某些情况：

def findSubstring(s, words): if not s or not words: return [] word_len = len(words[0]) total_words = len(words) total_len = word_len * total_words word_count = defaultdict(int) for word in words: word_count[word] += 1 result = [] for k in range(word_len): left = k curr_count = defaultdict(int) count = 0 for j in range(k, len(s) - word_len + 1, word_len): word = s[j:j + word_len] if word in word_count: curr_count[word] += 1 count += 1 while curr_count[word] > word_count[word]: left_word = s[left:left + word_len] curr_count[left_word] -= 1 left += word_len count -= 1 if count == total_words: result.append(left) left_word = s[left:left + word_len] curr_count[left_word] -= 1 left += word_len count -= 1 else: curr_count.clear() count = 0 left = j + word_len return result

3. 算法复杂度分析

3.1 时间复杂度

最优解的时间复杂度为O(n*m)，其中：

n是字符串s的长度
m是单个单词的长度

这是因为我们需要遍历字符串n次，每次检查m长度的单词。相比暴力解法的O(n!)，这是一个巨大的优化。

3.2 空间复杂度

空间复杂度主要来自哈希表的存储：

最坏情况下需要O(k)空间存储单词计数，k是不同单词的数量
滑动窗口过程中需要额外的O(k)空间

因此总空间复杂度为O(k)，在大多数情况下这是一个可以接受的代价。

4. 边界条件与测试用例

4.1 必须考虑的边界情况

在实际编码中，我发现以下几个边界条件必须特别注意：

空字符串或空单词列表
字符串长度小于所有单词总长度
单词列表中有重复单词
字符串中包含不属于单词列表的字符
多个有效子串重叠的情况

4.2 推荐测试用例

以下是我在调试过程中使用的关键测试用例：

test_cases = [ ("barfoothefoobarman", ["foo","bar"], [0,9]), ("wordgoodgoodgoodbestword", ["word","good","best","word"], []), ("barfoofoobarthefoobarman", ["bar","foo","the"], [6,9,12]), ("wordgoodgoodgoodbestword", ["word","good","best","good"], [8]), ("a", ["a"], [0]), ("aaaa", ["a","a"], [0,1,2]), ("aaaaaa", ["aaa","aaa"], [0]), ("aaaaaa", ["aa","aa"], [0,1,2]), ("", ["foo"], []), ("barfoo", [], []), ]