30. 串联所有单词的子串
目录
一、问题描述
二、解题思路
三、代码
四、复杂度分析
一、问题描述
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
二、解题思路
这个问题要求找到字符串 s 中的所有“串联子串”，这些子串由字符串数组 words 中的所有字符串组成，并且每个子串中的字符串都必须是 words 中的元素，且每个元素只能使用一次。具体的思路如下：
-
固定子串长度：每个子串的总长度是
words中每个字符串的长度乘以words中的字符串数量。即，子串的长度为len(words) * len(words[0])。 -
滑动窗口：我们可以通过滑动窗口的方式遍历字符串
s，每次检查长度为len(words) * len(words[0])的子串，判断该子串是否由words中的字符串拼接而成。 -
使用哈希表计数：为了判断一个子串是否包含
words中的所有字符串，我们可以使用一个哈希表记录words中每个字符串的出现次数，并在检查每个子串时，对其进行匹配。 -
边界条件：如果
s的长度小于len(words) * len(words[0])，则直接返回空列表。
具体步骤：
- 创建哈希表
word_count：用于记录words中每个字符串的出现次数。 - 遍历
s：从s的每个起点开始，取出长度为len(words) * len(words[0])的子串，并检查是否是由words中的字符串组成的。 - 滑动窗口检查：对每个子串使用另一个哈希表记录匹配到的字符串次数，逐个比较是否与
word_count一致。 - 返回结果：将所有符合条件的起始索引返回。
优化思路：
- 滑动窗口：通过滑动窗口，每次移动固定长度的窗口，而不是每次都重新构建和检查整个单词频率表。
- 跳过无效起点：如果某个起点的第一个单词不在
words中，可以直接跳过，而不是逐个检查。
三、代码
class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> result = new ArrayList<>();if (s == null || s.length() == 0 || words == null || words.length == 0) {return result;}int wordLength = words[0].length(); // 单个单词的长度int totalWordsLength = wordLength * words.length; // 所有单词拼接起来的总长度if (s.length() < totalWordsLength) {return result;}// 记录 words 中每个单词出现的次数Map<String, Integer> wordCount = new HashMap<>();for (String word : words) {wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);}// 遍历可能的起始位置for (int i = 0; i < wordLength; i++) {// 利用滑动窗口遍历整个字符串int left = i, right = i;int count = 0; // 记录匹配的单词数Map<String, Integer> seen = new HashMap<>();while (right + wordLength <= s.length()) {// 取出当前窗口右侧的单词String word = s.substring(right, right + wordLength);right += wordLength;if (wordCount.containsKey(word)) {seen.put(word, seen.getOrDefault(word, 0) + 1);count++;// 如果某个单词的数量超出了 words 中的要求，则需要移动左侧窗口while (seen.get(word) > wordCount.get(word)) {String leftWord = s.substring(left, left + wordLength);seen.put(leftWord, seen.get(leftWord) - 1);count--;left += wordLength;}// 当匹配到所有单词时，将当前左侧窗口的位置加入结果if (count == words.length) {result.add(left);}} else {// 如果当前单词不在 words 中，重置窗口seen.clear();count = 0;left = right;}}}return result;}
}
四、复杂度分析
- 外层循环遍历起始位置：
O(wordLength)。 - 内层循环遍历所有字符，每次移动
wordLength长度，整个遍历次数为O(n)，其中n是字符串s的长度。 - 因此，整体时间复杂度为
O(wordLength * n)，比之前直接比较每一个可能位置更高效。 - 空间复杂度：O(m)，因为我们需要额外的哈希表来记录
words中的单词以及窗口中的单词。