当前位置：首页 > article >正文

Leetcode 串联所有单词的子串

article 2024/12/22 14:47:35

在这里插入图片描述

算法思想（中文解释）

这道题目要求我们在字符串 s 中找到所有子串，这些子串是字符串数组 words 中所有单词的串联，并且每个单词只能使用一次，且顺序可以任意。下面是代码的算法思想：

1. 核心思路

分解问题：

因为每个单词长度相同，我们可以使用一个滑动窗口（Sliding Window）来检查所有可能的子串。
判断一个子串是否是所有单词的串联，可以通过比较单词的频次。

2. 步骤讲解

（1）初始化：

单词长度：用 wordLength 表示 words 中每个单词的长度（因为题目保证它们长度相同）。
总串联长度：totalLength = wordLength * words.length，因为子串的长度一定是所有单词的长度之和。
构造单词频次表：用 wordMap 记录 words 中每个单词的出现次数，便于后续比较。

（2）滑动窗口遍历：

从字符串 s 的每个位置开始，以长度为 totalLength 的窗口进行检查：
- 提取窗口中的子串 sub。
- 检查这个子串是否包含了 words 中所有单词且频次正确。

（3）子串验证：

对于窗口中的子串 sub，将其按照 wordLength 分割成一个个小单词。
检查这些小单词是否在 wordMap 中，并验证它们的出现频次是否超出限制：
- 如果某个单词不在 wordMap 中，立即返回 false；
- 如果某个单词出现的次数超过了在 wordMap 中的次数，也返回 false。
如果所有单词验证通过，则说明当前窗口位置是符合要求的，记录下起始索引。

3. 时间复杂度分析

构造单词频次表：O(m)，其中 m 是 words 的长度（即单词个数）。
滑动窗口遍历：外层遍历最多需要 n - totalLength + 1 次，n 是字符串 s 的长度。
验证子串：每次验证需要遍历窗口中的所有单词，复杂度为 O(m * wordLength)。

因此，总复杂度为：
[ O((n - totalLength + 1) \cdot m \cdot wordLength) ]
通常可以简化为 O(n * m)，适用于 s 较长和 words 较短的场景。

4. 代码逻辑解释

主函数：

wordMap：统计 words 中每个单词的出现频次。
滑动窗口遍历：通过 for 循环，遍历从 0 到 s.length() - totalLength 的所有可能起始位置。
子串验证：调用辅助函数 isValid() 检查是否符合要求。

辅助函数 `isValid`：

将子串 sub 分割成长度为 wordLength 的小单词。
使用 seen 哈希表记录窗口内每个单词的频次。
与 wordMap 进行比较，判断是否匹配。

5. 关键优化点

滑动窗口：避免暴力检查所有子串，只检查可能的窗口，减少不必要的计算。
哈希表：使用 wordMap 和 seen 快速判断频次关系，而不是逐一比较。
提前退出：在验证过程中，一旦发现不匹配的单词，立即退出验证，避免冗余计算。

6. 适用场景

该算法非常适用于以下情况：

单词长度固定，字符串较长。
words 中的单词个数适中（否则频次表的维护开销较大）。

通过滑动窗口和哈希表的结合，这个算法能够高效解决题目要求。

java solution

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if(s == null || s.length() == 0 || words.length == 0 || words == null) return result;

        //初始化辅助变量
        int wordsLength = words.length;
        int wordLength = words[0].length();
        int totalLength = wordLength * wordsLength;

        //创建频率统计哈希表
        Map<String, Integer> freq = new HashMap<>();
        for(String word:words) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }

        //变量字符串s
        for(int i = 0; i <= s.length() - totalLength; i++) {
            //首先获取窗口内的子串
            String sub = s.substring(i, i + totalLength); //substring 是左闭右开
            //然后验证此时窗口内的子串
            if(isValid(sub, freq, wordLength)) {
                result.add(i);
            }
        }
        return result;
    }
    private boolean isValid(String sub, Map<String, Integer> freq, int wordLength) {
        Map<String, Integer> seen = new HashMap<>(); //存储子串中的单词频次
        for(int j = 0; j < sub.length(); j += wordLength) {
            //提取子串中的单词
            String word = sub.substring(j, j + wordLength);
            if(!freq.containsKey(word)) { //如果这个单词不在freq频率表中,
                return false;
            }
            seen.put(word, seen.getOrDefault(word, 0) + 1); //更新seen中的频次
            if(seen.get(word) > freq.get(word)) { //如果频次超过freq的限制
                return false; 
            }
        }
        return true;
    }
}