| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Hard (39.58%) | 900 | - |
Tags
hash-table | two-pointers | string
Companies
Unknown
给定一个字符串 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 <= 1041 <= words.length <= 50001 <= words[i].length <= 30words[i] 和 s 由小写英文字母组成
Discussion | Solution
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
| // @lc code=start
impl Solution {
/// ## 解题思路
/// - 滑动窗口+hashmap
/// 1. hashmap记录遍历时,各个word出现的次数;
pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
use std::collections::HashMap;
let s = s.as_bytes();
let str_limit = s.len();
let word_cnt = words.len();
let word_size = words[0].len();
let mut res = Vec::new();
//统计words中各个word的次数, word -> (word_cnt, checked)
let mut word_map =
words
.iter()
.fold(HashMap::<&[u8], (usize, usize)>::new(), |mut map, word| {
map.entry(word.as_bytes()).or_default().0 += 1;
map
});
// 检查各个窗口中的字符串是否符合
for step in 0..word_size {
let mut l = step;
let mut cnt = 0; //
// 重置word_map
word_map.iter_mut().for_each(|(_, e)| {
e.1 = 0;
});
// 检查窗口内
while l + word_cnt * word_size <= str_limit {
// 检查窗口内各个word是否
while cnt < word_cnt {
match word_map.get_mut(&s[l+word_size*cnt..l + word_size*(cnt+1)].as_ref()) {
None => { //当前字符串不存在
l += (cnt+1) * word_size;
cnt = 0;
word_map.iter_mut().for_each(|(_, e)| {
e.1 = 0;
});
break;
}
Some(mut entry) => { //
entry.1 += 1; //checked 计数-1
cnt += 1;
if entry.1 > entry.0 { //如果当前word出现的次数大于words中的次数
if let Some(mut e) = word_map.get_mut(&s[l..l+word_size]){
e.1 -= 1;
}
l += word_size; //滑动窗口左边界
cnt -= 1; //窗口内word计数-1
break;
}
}
}
}
// 如果检查了word_cnt个word
if cnt == word_cnt {
if word_map.values().find(|&e| e.1 != e.0).is_none() {
res.push(l as i32);
}
// 将窗口内最左边界word的当前窗口计数-1
if let Some(mut e) = word_map.get_mut(&s[l..l+word_size]){
e.1 -= 1;
}
l += word_size; //滑动窗口左边界
cnt -= 1; //窗口内word计数-1
}
}
}
res
}
}
// @lc code=end
struct Solution;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
assert_eq!(Solution::find_substring("wordgoodgoodgoodbestword".to_string(),
vec!["word".to_string(),
"good".to_string(),
"best".to_string(),
"good".to_string()]),
vec![8]
);
}
}
|