# 0030. 串联所有单词的子串

### 题目地址（30. 串联所有单词的子串）

<https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/>

### 题目描述

```
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

 

示例 1：

输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：

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


```

### 前置知识

* 字符串
* 数组
* 哈希表

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

本题是要我们找出 words 中`所有单词按照任意顺序串联`形成的单词中恰好出现在 s 中的索引，因此顺序是不重要的。换句话说，我们只要统计每一个单词的出现情况即可。以题目中 s = "barfoothefoobarman", words = \["foo","bar"] 为例。 我们只需要统计 foo 出现了一次，bar 出现了一次即可。我们只需要在 s 中找到同样包含一次 foo 和一次 bar 的子串即可。由于 words 中的字符串都是等长的，因此编码上也会比较简单。

1. 我们的目标状态是 Counter(words)，即对 words 进行一次计数。
2. 我们只需从头开始遍历一次数组，每次截取 word 长度的字符，一共截取 words 长度次即可。
3. 如果我们截取的 Counter 和 Counter(words)一致，则加入到 res
4. 否则我们继续一个指针，继续执行步骤二
5. 重复执行这个逻辑直到达到数组尾部

### 关键点解析

* Counter

### 代码

语言支持：Python3, CPP

Python3 Code:

```python
from collections import Counter


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        res = []
        n = len(words)
        word_len = len(words[0])
        window_len = word_len * n
        target = Counter(words)
        i = 0
        while i < len(s) - window_len + 1:
            sliced = []
            start = i
            for _ in range(n):
                sliced.append(s[start:start + word_len])
                start += word_len
            if Counter(sliced) == target:
                res.append(i)
            i += 1
        return res
```

CPP Code:

```cpp

class Solution {
private:
    int len, n;
    string s;
    bool rec(int i, unordered_map<string, int> &m, int cnt) {
        if (cnt == n) return true;
        int &v = m[s.substr(i, len)];
        if (v) {
            v--;
            bool ret = rec(i + len, m, cnt + 1);
            v++;
            return ret;
        }
        return false;
    }
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if (words.empty()) return {};
        this->s = s;
        len = words[0].size();
        n = words.size();
        unordered_map<string, int> m;
        for (string word : words) ++m[word];
        int end = s.size() - n * len;
        vector<int> v;
        for (int i = 0; i <= end; ++i) {
            if (rec(i, m, 0)) v.push_back(i);
        }
        return v;
    }
};
```

**复杂度分析**

其中 N 为 words 中的总字符数。

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/bbl6tw.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/30.substring-with-concatenation-of-all-words.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.