LeetCode题练习与总结：串联所有单词的子串

本文主要是介绍LeetCode题练习与总结：串联所有单词的子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

二、解题思路

1. 确定单词长度：首先，我们需要知道每个单词的长度，这可以通过检查 words 数组中的第一个元素得到。

2. 计算重复因子：由于所有单词长度相同，我们可以计算 s 中的字符数与单词长度的比值，这个比值决定了 s 中可以有多少个完整的 words 组合。

3. 创建哈希表：为了快速查找单词，我们可以创建一个哈希表，其中键是单词，值是该单词在 words 数组中出现的次数。

4. 滑动窗口：使用滑动窗口的方法遍历字符串 s，窗口大小为单词长度。在遍历过程中，我们检查窗口内的单词是否在哈希表中，并且它们的计数是否正确。

5. 更新答案：每当我们找到一个有效的串联子串，我们就记录下这个子串在 s 中的起始索引，并将其添加到结果列表中。

6. 返回结果：最后，我们返回包含所有有效起始索引的列表。

三、具体代码

import java.util.*;class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> result = new ArrayList<>();if (s == null || words == null || words.length == 0 || words[0].length() == 0) {return result;}int wordLen = words[0].length();int totalLen = words.length * wordLen;Map<String, Integer> wordMap = new HashMap<>();for (String word : words) {wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);}int sLen = s.length();if (sLen < totalLen) {return result;}for (int i = 0; i <= sLen - totalLen; i++) {boolean valid = true;Map<String, Integer> windowMap = new HashMap<>(wordMap);for (int j = i; j < i + totalLen; j += wordLen) {String windowWord = s.substring(j, j + wordLen);if (!windowMap.containsKey(windowWord)) {valid = false;break;}windowMap.put(windowWord, windowMap.get(windowWord) - 1);if (windowMap.get(windowWord) < 0) {valid = false;break;}}if (valid) {result.add(i);}}return result;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 初始化哈希表的时间复杂度是 O(N)，其中 N 是 words 数组的长度。
• 遍历字符串 s 的外层循环的时间复杂度是 O(S - totalLen + 1)，其中 S 是 s 的长度。
• 内层循环的时间复杂度是 O(M)，其中 M 是 words 数组中每个单词的长度，也就是单词的固定长度。
• 内层循环中的哈希表操作（查找和更新）的时间复杂度平均是 O(1)。
• 将这些组合起来，总的时间复杂度是 O(N + (S - totalLen + 1) * M)。
• 由于 M 是常数，我们可以将其简化为 O(N + S)。

2. 空间复杂度

• 哈希表 wordMap 存储了所有单词及其出现次数，空间复杂度是 O(N)。
• 在遍历过程中，我们创建了一个与 wordMap 大小相同的临时哈希表 windowMap，其空间复杂度也是 O(N)。
• 结果列表 result 的空间复杂度取决于找到的串联子串的数量，最坏情况下是 O(S - totalLen + 1)，但这是一个与输入数据相关的值，不是固定的。
• 综合考虑，总的空间复杂度是 O(N + (S - totalLen + 1))，其中 O(N) 是主要部分，因为结果列表的大小通常不会超过 O(N)。
• 在实际应用中，我们通常会忽略常数因子和较小的项，所以可以简化为 O(N)。

五、总结知识点

1. 字符串处理：

• 使用 String 类的 substring 方法来获取字符串的子串。

2. 数据结构：

• 使用 HashMap 来存储单词及其出现次数，这允许我们快速地进行查找和更新操作。
• 使用 ArrayList 来存储结果，这是一个动态数组，可以方便地添加元素。

3. 循环结构：

• 使用 for 循环来遍历字符串 s 的所有可能的子串起始位置。
• 使用嵌套的 for 循环（滑动窗口）来检查当前窗口内的单词是否符合要求。

4. 条件判断：

• 使用 if 语句和 boolean 类型的变量 valid 来判断当前窗口是否包含所有单词。

5. 异常处理：

• 在代码开始处，对输入参数进行空值检查，确保 s 和 words 不为 null，且 words 数组不为空，且每个单词的长度不为零。

6. 边界条件处理：

• 在开始遍历之前，检查字符串 s 的长度是否足够包含所有单词的串联，如果不够，则直接返回空的结果列表。

7. 空间复用：

• 在每次外层循环迭代时，创建一个新的 HashMap windowMap 来跟踪当前窗口内的单词出现次数，这样可以避免在内层循环中修改外部循环的状态。

8. 集合操作：

• 使用 Map 的 getOrDefault 方法来获取键对应的值，如果键不存在则返回默认值（这里默认值为 0）。

9. 返回值处理：

• 在找到有效的串联子串时，将起始索引添加到结果列表中，并在最后返回这个列表。

10.代码的可读性和维护性：

• 使用有意义的变量名（如 wordLen, totalLen, wordMap, windowMap, valid）来提高代码的可读性。
• 使用 boolean 变量 valid 来简化条件判断，使代码更加清晰。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

这篇关于LeetCode题练习与总结：串联所有单词的子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---