30. 串联所有单词的子串

1. 题目

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef""abefcd""cdabef""cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

1
2
3
4
5
6
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

1
2
3
4
5
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3:

1
2
3
4
5
6
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i]s 由小写英文字母组成

2. 思路

  • 整体利用滑动窗口的做法,配合着哈希表,对固定区间范围内的字符串进行一一比对

  • 初始化前缀哈希表preMap变量,记录的是首个字符对应的单词集合

  • 初始化计数哈希表countMap变量,记录的是每个单词的数量

  • 初始化length变量用于记录words数组中所有单词加起来的总长度,用于定义滑动窗口的大小,因为题目要求需要包含所有的单词

  • 初始化左指针l与右指针r,每次判断滑动窗口范围内的字符是否能够包含所有的单词

    • 如果能够包含,则记录在结果集result当中
  • 每次检查完窗口范围内的匹配结果后,左指针l与右指针r同时向右前进一格,如下图所示

  • 当检查滑动窗口内的字符是否能够匹配所有的单词时,可以用到前缀哈希表preMap找到对应滑动窗口内的单词集合

    • 如果无法在前缀哈希表preMap当中找到对应的单词集合,则表示窗口范围内的子串肯定无法串联所有的单词,此时返回匹配失败
    • 如果能够在前缀哈希表preMap当中找到对应的单词集合,则继续判断遍历每个单词是否能够匹配到子串中
    • 最终检查结果需要确保所有的单词都使用,过程中需要保证每个单词只能使用对应出现的次数

93fb4436340daedd835496ea52c7b5c16761bc115f621dc656c625e044038379-动态图

图源动画演示 30. 串联所有单词的子串

3. 代码

以下代码还有一个优化点,即是使用计数不需要每次都重新开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
var preMap = new HashMap<Character, List<String>>();
var countMap = new HashMap<String, Integer>();
var result = new ArrayList<Integer>();
var length = 0;

for (var i = 0; i < words.length; ++i) {
var word = words[i];
length += word.length();

var currentCount = countMap.getOrDefault(word, 0) + 1;
countMap.put(word, currentCount);

var firstChar = word.charAt(0);
var prefixIndexs = preMap.getOrDefault(firstChar, new ArrayList<String>());
prefixIndexs.add(word);
preMap.put(firstChar, prefixIndexs);
}

if (s.length() < length) {
return result;
}

var l = 0;
var r = length - 1;

while (r < s.length()) {
var ch = s.charAt(l);

if (match(s, new HashMap<>(countMap), preMap, l, r, words.length)) {
result.add(l);
}

l++;
r++;
}

return result;
}

private boolean match(
String originStr,
Map<String, Integer> countMap,
Map<Character, List<String>> preMap,
int startIndex,
int endIndex,
int totalCount
) {
var i = startIndex;
while (i <= endIndex) {
var ch = originStr.charAt(i);
var prefixIndexs = preMap.getOrDefault(ch, Collections.emptyList());
if (prefixIndexs.isEmpty()) {
return false;
}

var match = false;

for (var word : prefixIndexs) {
var count = countMap.get(word);
if (count >= 1 && match(originStr, word, i)) {
match = true;
i += word.length();
countMap.put(word, count - 1);
totalCount--;
break;
}
}

if (!match) {
return false;
}
}

return totalCount == 0;
}

private boolean match(String originStr, String targetStr, int startIndex) {
var i = startIndex;
var j = 0;

while(i < originStr.length() && j < targetStr.length()) {
if (originStr.charAt(i) == targetStr.charAt(j)) {
i++;
j++;
} else {
return false;
}
}

return j == targetStr.length();
}
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

image-20230818005148271