You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
Example 1:
Input: s = “barfoothefoobarman”, words = [“foo”,“bar”]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
Input: s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
Output: []
Example 3:
Input: s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
Output: [6,9,12]
Constraints:
- 1 <= s.length <= 104
- 1 <= words.length <= 5000
- 1 <= words[i].length <= 30
- s and words[i] consist of lowercase English letters.
这题作为 hard 的题目, 难度其实不大,思路比较简单, 但是挺考验将思路转化为代码的能力。
先说思路, 因为 words 里面的单词都是固定长度的, 比如[‘aaa’, ‘bbb’, ‘ccc’], 其 length=3, 所以对于任何字符串 s, 我们只需要对 s[0…], s[1…], s[2…]进行检查就可以了, 因为 s[3…], s[4…], s[5…]这些分别都会在 s[0…], s[1…], s[2…]中检查到。对于每一个子串的检查其实也不复杂, 建立一个 queue, 每次将 s[i…i+length]拿出来, 检查 words 里是否有这个单词,如果有则将这个单词 push 到 queue 中, 然后检查 queue 中的该单词是不是有超出 words 里面约定的数量的, 如果有那就需要持续 left pop queue, 直到 queue 里的该单词数量等于约定数量, 然后就可以检查 queue 里的元素及其数量是不是与 words 中的一致, 如果一致则将此时形成该 queue 的起始 index 放到答案中
use std::collections::HashMap;
impl Solution {
fn check(curr: &Vec<String>, target: &HashMap<String, i32>) -> bool {
let m = curr.into_iter().fold(HashMap::new(), |mut m, v| {
*m.entry(v).or_insert(0) += 1;
m
});
if m.len() != target.len() {
return false;
}
for (k, v) in m {
if v != *target.get(k).unwrap() {
return false;
}
}
true
}
fn find(
chars: &[char],
words: &HashMap<String, i32>,
length: usize,
offset: usize,
) -> Vec<i32> {
let mut q = Vec::new();
let mut start = 0;
let mut end = length;
let mut ans = Vec::new();
while end <= chars.len() {
let word: String = chars[end - length..end].into_iter().collect();
if !words.contains_key(&word) {
q.clear();
start = end;
end = end + length;
continue;
}
let required = words.get(&word).unwrap();
q.push(word.clone());
let mut count = q.iter().filter(|&v| v == &word).count();
while count as i32 > *required {
let head = q.remove(0);
start += length;
if head == word {
count -= 1;
}
}
if Solution::check(&q, &words) {
ans.push(start as i32 + offset as i32);
}
end += length;
}
ans
}
pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
let length = words[0].len();
let words: HashMap<String, i32> = words.into_iter().fold(HashMap::new(), |mut m, v| {
*m.entry(v).or_insert(0) += 1;
m
});
let chars: Vec<char> = s.chars().collect();
let mut ans = Vec::new();
for i in 0..length {
ans.append(&mut Solution::find(&chars[i..], &words, length, i));
}
ans
}
}