LeetCode 30. 串联所有单词的子串

Categories:

题目描述
思路分析
1. 解法一：按单词长度滑动窗口（推荐）
相似题目

题目描述

✅ 30. 串联所有单词的子串

思路分析

解法一：按单词长度滑动窗口（推荐）

核心思路：

所有单词长度相同，设为 L，总窗口长度为 L * m。

以 0..L-1 为起点分组滑动，窗口每次移动 L。

用哈希表记录窗口内单词频次，超出时移动左指针调整。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(m)，其中 m 表示单词数量。

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

        int wordLen = words[0].length();
        int wordCount = words.length;
        int totalLen = wordLen * wordCount;

        Map<String, Integer> need = new HashMap<>();
        for (String w : words) {
            need.put(w, need.getOrDefault(w, 0) + 1);
        }

        for (int offset = 0; offset < wordLen; offset++) {
            int left = offset;
            int matched = 0;
            Map<String, Integer> window = new HashMap<>();

            for (int right = offset; right + wordLen <= s.length(); right += wordLen) {
                String word = s.substring(right, right + wordLen);

                if (!need.containsKey(word)) {
                    // 词不在目标中，重置窗口
                    window.clear();
                    matched = 0;
                    left = right + wordLen;
                    continue;
                }

                window.put(word, window.getOrDefault(word, 0) + 1);
                if (window.get(word) <= need.get(word)) {
                    matched++;
                }

                // 频次超出则移动左指针
                while (window.get(word) > need.get(word)) {
                    String leftWord = s.substring(left, left + wordLen);
                    window.put(leftWord, window.get(leftWord) - 1);
                    if (window.get(leftWord) < need.get(leftWord)) {
                        matched--;
                    }
                    left += wordLen;
                }

                if (matched == wordCount) {
                    res.add(left);
                    String leftWord = s.substring(left, left + wordLen);
                    window.put(leftWord, window.get(leftWord) - 1);
                    matched--;
                    left += wordLen;
                }
            }
        }

        return res;
    }
}

func findSubstring(s string, words []string) []int {
    res := make([]int, 0)
    if len(words) == 0 {
        return res
    }

    wordLen := len(words[0])
    wordCount := len(words)
    totalLen := wordLen * wordCount
    if len(s) < totalLen {
        return res
    }

    need := make(map[string]int)
    for _, w := range words {
        need[w]++
    }

    for offset := 0; offset < wordLen; offset++ {
        left := offset
        matched := 0
        window := make(map[string]int)

        for right := offset; right+wordLen <= len(s); right += wordLen {
            word := s[right : right+wordLen]

            if _, ok := need[word]; !ok {
                // 词不在目标中，重置窗口
                window = make(map[string]int)
                matched = 0
                left = right + wordLen
                continue
            }

            window[word]++
            if window[word] <= need[word] {
                matched++
            }

            // 频次超出则移动左指针
            for window[word] > need[word] {
                leftWord := s[left : left+wordLen]
                window[leftWord]--
                if window[leftWord] < need[leftWord] {
                    matched--
                }
                left += wordLen
            }

            if matched == wordCount {
                res = append(res, left)
                leftWord := s[left : left+wordLen]
                window[leftWord]--
                matched--
                left += wordLen
            }
        }
    }

    return res
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
567. 字符串的排列	中等	滑动窗口
992. K 个不同整数的子数组	困难	滑动窗口
30. 串联所有单词的子串	困难	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/69908263