跳到主要内容

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

本节目标

按词长余数拆分起点，用单词频次窗口寻找完整串联位置。

这道题是字符串综合中的定长单词窗口母题。目标不是匹配字符集合，而是让窗口恰好包含给定单词的全部频次。

查看原题

题意与约束​

给定字符串 s 和若干长度相同的单词，找出所有起点，使从该位置开始的子串能够由这些单词以任意顺序首尾连接。重复单词必须按给定次数出现。

设单词长度为 L、单词数量为 m，合法窗口长度固定为 L × m。

为什么要按词长余数分组​

从起点 offset 开始，每次向右移动 L 个字符，就会始终落在同一个余数类。offset = 0..L-1 的这些扫描覆盖全部可能起点，同时保证窗口的每次加入和移除都是一个完整单词。

若逐字符移动同一个窗口，单词边界会不断变化，已有频次无法直接复用。

窗口不变量​

need 保存目标词频，window 保存当前窗口词频，used 是窗口中的单词数量。

加入一个目标单词后：

  1. 若该词频次超过需要，就从左侧按单词收缩，直到频次恢复合法；
  2. 若 used == m，当前左端就是答案；
  3. 记录答案后移除最左单词，为可能重叠的下一个窗口留出位置。

遇到不在 need 中的单词时，当前余数类里的连续候选被截断，窗口必须整体清空并从下一个单词重新开始。

代码实现​

两种语言都对每个词长余数维护独立窗口，并用固定种子的暴力对照测试覆盖重复词、重叠与无匹配情况。

C++17
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> answer;
        if (words.empty()) {
            return answer;
        }

        int wordLength = static_cast<int>(words[0].size());
        int wordCount = static_cast<int>(words.size());
        int totalLength = wordLength * wordCount;
        if (totalLength > static_cast<int>(s.size())) {
            return answer;
        }

        unordered_map<string, int> need;
        for (const string& word : words) {
            need[word]++;
        }

        for (int offset = 0; offset < wordLength; offset++) {
            unordered_map<string, int> window;
            int left = offset;
            int used = 0;

            for (
                int right = offset;
                right + wordLength <= static_cast<int>(s.size());
                right += wordLength
            ) {
                string word = s.substr(right, wordLength);
                if (!need.count(word)) {
                    window.clear();
                    used = 0;
                    left = right + wordLength;
                    continue;
                }

                window[word]++;
                used++;
                while (window[word] > need[word]) {
                    string leftWord = s.substr(left, wordLength);
                    window[leftWord]--;
                    left += wordLength;
                    used--;
                }

                if (used == wordCount) {
                    answer.push_back(left);
                    string leftWord = s.substr(left, wordLength);
                    window[leftWord]--;
                    left += wordLength;
                    used--;
                }
            }
        }

        return answer;
    }
};

复杂度分析​

设 n = |s|，单词长度为 L。所有余数类合计处理 O(n) 个单词片段；当前实现创建长度为 L 的子串，因此时间复杂度为 O(nL)，哈希操作按均摊 O(1) 计算。额外空间复杂度为 O(uL)，其中 u 是不同目标单词数。

易错点​

  • 忽略重复单词，只用集合判断是否出现。
  • 某个单词过量时只移除一次，而不是持续收缩到合法。
  • 找到完整窗口后不移动左端，漏掉后续重叠答案。
  • 把不同余数类放进同一个窗口，导致切词边界错位。

模式迁移​

它是第四章滑动窗口框架的定长块版本：窗口加入和移除的最小单位从字符改为等长单词。遇到固定长度记录、编码块或分组 token 时，也可以先按块长余数拆分，再复用同样的频次不变量。