解题思路与实现 - 串联所有单词的子串
问题描述
给定一个字符串 s 和一个字符串数组 words，数组中所有字符串长度相同。s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。找出所有串联子串在 s 中的起始索引。
示例
- 输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：子串 “barfoo” 和 “foobar” 都是以 ["foo","bar"] 顺序排列的连接。 - 输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：无符合条件的串联子串。 - 输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：子串 “foobarthe”、“barthefoo” 和 “thefoobar” 都是以 ["bar","foo","the"] 顺序排列的连接。
解题思路
使用滑动窗口（双指针）和哈希表的方法解决该问题：
- 将 words 中的所有单词存入哈希表 wordCount，记录每个单词的出现次数。
- 遍历字符串 s，以每个可能的起始位置作为窗口的起点，通过滑动窗口判断是否能匹配所有单词。
- 窗口的大小应为 words 中所有单词的总长度。
- 滑动窗口每次向右移动一个单词长度，维护一个窗口中包含的单词计数 currentWords。
- 若窗口中的单词与 words 中的单词匹配，则将起点加入结果列表。
算法实现
public List<Integer> findSubstring(String s, String[] words) { List<Integer> result = new ArrayList<>(); if (s == null || s.isEmpty() || words == null || words.length == 0) { return result; } Map<String, Integer> wordCount = new HashMap<>(); int wordLength = words[0].length(); int totalLength = wordLength * words.length; for (String word : words) { wordCount.put(word, wordCount.getOrDefault(word, 0) + 1); } for (int i = 0; i <= s.length() - totalLength; i++) { Map<String, Integer> currentWords = new HashMap<>(); int j = 0; while (j < words.length) { String currentWord = s.substring(i + j * wordLength, i + (j + 1) * wordLength); if (!wordCount.containsKey(currentWord)) { break; } currentWords.put(currentWord, currentWords.getOrDefault(currentWord, 0) + 1); if (currentWords.get(currentWord) > wordCount.getOrDefault(currentWord, 0)) { break; } j++; } if (j == words.length) { result.add(i); } } return result; }
复杂度分析
- 时间复杂度：O(n * m)，其中 n 是字符串 s 的长度，m 是单词数组 words 的长度。
- 空间复杂度：O(m)，哈希表 wordCount 和 currentWords 的空间复杂度为单词数组 words 的长度。
测试与验证
设计不同测试用例，包括空字符串、单个单词、多个单词等情况，验证算法的正确性和效率。
总结
通过本文的详细解题思路和算法实现，可以有效地解决给定字符串中找出所有串联子串的起始索引的问题。利用滑动窗口和哈希表的方法，可以高效地实现该算法。
