30. 串联所有单词的子串

题目描述

输入字符串 s 和字符串数组 words。words 里所有单词的长度都相同，单词可能重复。

把 words 中的全部单词各用一次、按某种顺序首尾相接，得到的字符串称为一种串联。例如 words = ["ab","cd","ef"] 时，"abcdef"、"cdabef"、"efcdab" 等都是串联，但 "acdbef" 不是。

找出 s 中所有恰好等于某种串联的子串，返回它们的起始下标，顺序不限。没有则返回空数组。

示例 1

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]

解释：串联长度为 6。下标 0 处是 "barfoo"，下标 9 处是 "foobar"，都符合。

示例 2

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

解释：串联长度为 16，需要两个 word、一个 good、一个 best，s 中没有这样的子串。

示例 3

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

解释：串联长度为 9。下标 6、9、12 处分别是 "foobarthe"、"barthefoo"、"thefoobar"。

数据范围

1 <= s.length <= 10^4
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 都只含小写英文字母。

解题思路：分组滑动窗口

设单词长 w。只要把 s 按起点 off（0 到 w-1）切成长度为 w 的块，答案就是「连续 m 块恰好等于 words 的多重集」。对每个 off 用滑动窗口：右端每次加入一个块；若块不是单词，窗口清空并跳到它后面；若某单词次数超过需要，就从左端一块一块移出；窗口恰好含 m 块时记录 left。

为什么正确

窗口 s[left:right+w] 由若干个完整单词组成，且每个单词的次数不超过 need；cnt 是窗口内的块数。

复杂度分析

时间 O(n · w)：每个 off 下每块最多进出窗口各一次，切块花 O(w)。空间 O(m · w)。

易错点

words 可能有重复单词，必须按次数比较，不能用集合。另外只从下标 0 切块会漏掉起点不是 w 的倍数的答案，要枚举 w 个起点。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        w, m = len(words[0]), len(words)
        need = collections.Counter(words)
        res = []
        for off in range(w):
            left, cnt = off, 0
            seen = collections.Counter()
            for right in range(off, len(s) - w + 1, w):
                word = s[right:right + w]
                if word not in need:
                    seen.clear()
                    cnt = 0
                    left = right + w
                    continue
                seen[word] += 1
                cnt += 1
                while seen[word] > need[word]:
                    seen[s[left:left + w]] -= 1
                    cnt -= 1
                    left += w
                if cnt == m:
                    res.append(left)
        return res

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int w = words[0].length(), m = words.length;
        Map<String, Integer> need = new HashMap<>();
        for (String x : words) need.merge(x, 1, Integer::sum);
        List<Integer> res = new ArrayList<>();
        for (int off = 0; off < w; off++) {
            int left = off, cnt = 0;
            Map<String, Integer> seen = new HashMap<>();
            for (int right = off; right + w <= s.length(); right += w) {
                String word = s.substring(right, right + w);
                if (!need.containsKey(word)) {
                    seen.clear();
                    cnt = 0;
                    left = right + w;
                    continue;
                }
                seen.merge(word, 1, Integer::sum);
                cnt++;
                while (seen.get(word) > need.get(word)) {
                    seen.merge(s.substring(left, left + w), -1, Integer::sum);
                    cnt--;
                    left += w;
                }
                if (cnt == m) {
                    res.add(left);
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int w = words[0].size(), m = words.size();
        unordered_map<string, int> need;
        for (auto& x : words) need[x]++;
        vector<int> res;
        for (int off = 0; off < w; off++) {
            int left = off, cnt = 0;
            unordered_map<string, int> seen;
            for (int right = off; right + w <= (int)s.size(); right += w) {
                string word = s.substr(right, w);
                if (!need.count(word)) {
                    seen.clear();
                    cnt = 0;
                    left = right + w;
                    continue;
                }
                seen[word]++;
                cnt++;
                while (seen[word] > need[word]) {
                    seen[s.substr(left, w)]--;
                    cnt--;
                    left += w;
                }
                if (cnt == m) {
                    res.push_back(left);
                }
            }
        }
        return res;
    }
};

func findSubstring(s string, words []string) []int {
    w, m := len(words[0]), len(words)
    need := map[string]int{}
    for _, x := range words {
        need[x]++
    }
    res := []int{}
    for off := 0; off < w; off++ {
        left, cnt := off, 0
        seen := map[string]int{}
        for right := off; right+w <= len(s); right += w {
            word := s[right : right+w]
            if _, ok := need[word]; !ok {
                seen = map[string]int{}
                cnt = 0
                left = right + w
                continue
            }
            seen[word]++
            cnt++
            for seen[word] > need[word] {
                seen[s[left:left+w]]--
                cnt--
                left += w
            }
            if cnt == m {
                res = append(res, left)
            }
        }
    }
    return res
}

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    const w = words[0].length, m = words.length;
    const need = new Map();
    for (const x of words) need.set(x, (need.get(x) || 0) + 1);
    const res = [];
    for (let off = 0; off < w; off++) {
        let left = off, cnt = 0;
        const seen = new Map();
        for (let right = off; right + w <= s.length; right += w) {
            const word = s.substring(right, right + w);
            if (!need.has(word)) {
                seen.clear();
                cnt = 0;
                left = right + w;
                continue;
            }
            seen.set(word, (seen.get(word) || 0) + 1);
            cnt++;
            while (seen.get(word) > need.get(word)) {
                const lw = s.substring(left, left + w);
                seen.set(lw, seen.get(lw) - 1);
                cnt--;
                left += w;
            }
            if (cnt === m) {
                res.push(left);
            }
        }
    }
    return res;
};

function findSubstring(s: string, words: string[]): number[] {
    const w = words[0].length, m = words.length;
    const need = new Map<string, number>();
    for (const x of words) need.set(x, (need.get(x) || 0) + 1);
    const res: number[] = [];
    for (let off = 0; off < w; off++) {
        let left = off, cnt = 0;
        const seen = new Map<string, number>();
        for (let right = off; right + w <= s.length; right += w) {
            const word = s.substring(right, right + w);
            if (!need.has(word)) {
                seen.clear();
                cnt = 0;
                left = right + w;
                continue;
            }
            seen.set(word, (seen.get(word) || 0) + 1);
            cnt++;
            while (seen.get(word)! > need.get(word)!) {
                const lw = s.substring(left, left + w);
                seen.set(lw, seen.get(lw)! - 1);
                cnt--;
                left += w;
            }
            if (cnt === m) {
                res.push(left);
            }
        }
    }
    return res;
}

载入编辑器，自己跑一遍 →

其他解法

枚举起点对每个位置重新计数，是 O(n·m·w)；分组滑动窗口按起点对 w 取余分成 w 组，每组内左右端只向右移动，去掉了因子 m。

解法 2：枚举起点 + 计数时间 O(n·m·w)，空间 O(m·w)

用哈希表 need 统计每个单词需要的次数。枚举每个起点 i，从 i 开始连续切出 m 个长为 w 的单词，用 seen 计数。某个单词不在 need 中或已经达到需要次数时立即停止；顺利切完 m 个就记录 i。

每个起点独立判断，正确性容易确认，适合作为第一版思路和对拍基准。相邻起点之间没有复用信息，单词多时比分组滑动窗口慢很多。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        w, m = len(words[0]), len(words)
        need = collections.Counter(words)
        res = []
        for i in range(len(s) - m * w + 1):
            seen = collections.Counter()
            j = 0
            while j < m:
                word = s[i + j * w:i + (j + 1) * w]
                if seen[word] >= need[word]:
                    break
                seen[word] += 1
                j += 1
            if j == m:
                res.append(i)
        return res

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int w = words[0].length(), m = words.length;
        Map<String, Integer> need = new HashMap<>();
        for (String x : words) need.merge(x, 1, Integer::sum);
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i + m * w <= s.length(); i++) {
            Map<String, Integer> seen = new HashMap<>();
            int j = 0;
            while (j < m) {
                String word = s.substring(i + j * w, i + (j + 1) * w);
                if (seen.getOrDefault(word, 0) >= need.getOrDefault(word, 0)) break;
                seen.merge(word, 1, Integer::sum);
                j++;
            }
            if (j == m) res.add(i);
        }
        return res;
    }
}

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int w = words[0].size(), m = words.size(), n = s.size();
        unordered_map<string, int> need;
        for (auto& x : words) need[x]++;
        vector<int> res;
        for (int i = 0; i + m * w <= n; i++) {
            unordered_map<string, int> seen;
            int j = 0;
            while (j < m) {
                string word = s.substr(i + j * w, w);
                auto it = need.find(word);
                if (it == need.end() || seen[word] >= it->second) break;
                seen[word]++;
                j++;
            }
            if (j == m) res.push_back(i);
        }
        return res;
    }
};

func findSubstring(s string, words []string) []int {
    w, m := len(words[0]), len(words)
    need := map[string]int{}
    for _, x := range words {
        need[x]++
    }
    res := []int{}
    for i := 0; i+m*w <= len(s); i++ {
        seen := map[string]int{}
        j := 0
        for j < m {
            word := s[i+j*w : i+(j+1)*w]
            if seen[word] >= need[word] {
                break
            }
            seen[word]++
            j++
        }
        if j == m {
            res = append(res, i)
        }
    }
    return res
}

var findSubstring = function(s, words) {
    const w = words[0].length, m = words.length;
    const need = new Map();
    for (const x of words) need.set(x, (need.get(x) || 0) + 1);
    const res = [];
    for (let i = 0; i + m * w <= s.length; i++) {
        const seen = new Map();
        let j = 0;
        while (j < m) {
            const word = s.slice(i + j * w, i + (j + 1) * w);
            const c = seen.get(word) || 0;
            if (c >= (need.get(word) || 0)) break;
            seen.set(word, c + 1);
            j++;
        }
        if (j === m) res.push(i);
    }
    return res;
};

function findSubstring(s: string, words: string[]): number[] {
    const w = words[0].length, m = words.length;
    const need = new Map<string, number>();
    for (const x of words) need.set(x, (need.get(x) || 0) + 1);
    const res: number[] = [];
    for (let i = 0; i + m * w <= s.length; i++) {
        const seen = new Map<string, number>();
        let j = 0;
        while (j < m) {
            const word = s.slice(i + j * w, i + (j + 1) * w);
            const c = seen.get(word) || 0;
            if (c >= (need.get(word) || 0)) break;
            seen.set(word, c + 1);
            j++;
        }
        if (j === m) res.push(i);
    }
    return res;
}

滑动窗口专题的其他题目

查看滑动窗口全部题目 →