第六章 - 高频考题(困难)
0030. 串联所有单词的子串

题目地址(30. 串联所有单词的子串)

题目描述

1
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
2
3
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
4
5
6
7
示例 1:
8
9
输入:
10
s = "barfoothefoobarman",
11
words = ["foo","bar"]
12
输出:[0,9]
13
解释:
14
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
15
输出的顺序不重要, [9,0] 也是有效答案。
16
示例 2:
17
18
输入:
19
s = "wordgoodgoodgoodbestword",
20
words = ["word","good","best","word"]
21
输出:[]
Copied!

前置知识

  • 字符串
  • 数组
  • 哈希表

公司

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

思路

本题是要我们找出 words 中所有单词按照任意顺序串联形成的单词中恰好出现在 s 中的索引,因此顺序是不重要的。换句话说,我们只要统计每一个单词的出现情况即可。以题目中 s = "barfoothefoobarman", words = ["foo","bar"] 为例。 我们只需要统计 foo 出现了一次,bar 出现了一次即可。我们只需要在 s 中找到同样包含一次 foo 和一次 bar 的子串即可。由于 words 中的字符串都是等长的,因此编码上也会比较简单。
  1. 1.
    我们的目标状态是 Counter(words),即对 words 进行一次计数。
  2. 2.
    我们只需从头开始遍历一次数组,每次截取 word 长度的字符,一共截取 words 长度次即可。
  3. 3.
    如果我们截取的 Counter 和 Counter(words)一致,则加入到 res
  4. 4.
    否则我们继续一个指针,继续执行步骤二
  5. 5.
    重复执行这个逻辑直到达到数组尾部

关键点解析

  • Counter

代码

语言支持:Python3, CPP
Python3 Code:
1
from collections import Counter
2
3
4
class Solution:
5
def findSubstring(self, s: str, words: List[str]) -> List[int]:
6
if not s or not words:
7
return []
8
res = []
9
n = len(words)
10
word_len = len(words[0])
11
window_len = word_len * n
12
target = Counter(words)
13
i = 0
14
while i < len(s) - window_len + 1:
15
sliced = []
16
start = i
17
for _ in range(n):
18
sliced.append(s[start:start + word_len])
19
start += word_len
20
if Counter(sliced) == target:
21
res.append(i)
22
i += 1
23
return res
Copied!
CPP Code:
1
class Solution {
2
private:
3
int len, n;
4
string s;
5
bool rec(int i, unordered_map<string, int> &m, int cnt) {
6
if (cnt == n) return true;
7
int &v = m[s.substr(i, len)];
8
if (v) {
9
v--;
10
bool ret = rec(i + len, m, cnt + 1);
11
v++;
12
return ret;
13
}
14
return false;
15
}
16
public:
17
vector<int> findSubstring(string s, vector<string>& words) {
18
if (words.empty()) return {};
19
this->s = s;
20
len = words[0].size();
21
n = words.size();
22
unordered_map<string, int> m;
23
for (string word : words) ++m[word];
24
int end = s.size() - n * len;
25
vector<int> v;
26
for (int i = 0; i <= end; ++i) {
27
if (rec(i, m, 0)) v.push_back(i);
28
}
29
return v;
30
}
31
};
Copied!
复杂度分析
其中 N 为 words 中的总字符数。
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。