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 <= 104s consists of lower-case English letters.1 <= words.length <= 50001 <= words[i].length <= 30words[i] consists of lower-case English letters.struct Solution;
use std::collections::HashMap;
impl Solution {
fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
let n = s.len();
if n == 0 {
return vec![];
}
let mut count: HashMap<&str, usize> = HashMap::new();
let m = words.len();
if m == 0 {
return vec![];
}
let size = words[0].len();
if m * size > n {
return vec![];
}
for w in &words {
*count.entry(w).or_default() += 1;
}
let mut res = vec![];
'outer: for i in 0..=n - m * size {
let mut cur: HashMap<&str, usize> = HashMap::new();
for j in 0..m {
let w = &s[i + j * size..i + (j + 1) * size];
if let Some(x) = count.get(w) {
let y = cur.entry(w).or_default();
*y += 1;
if *y > *x {
continue 'outer;
}
} else {
continue 'outer;
}
}
res.push(i as i32);
}
res
}
}
#[test]
fn test() {
let s = "barfoothefoobarman".to_string();
let words = vec_string!["foo", "bar"];
let res = vec![0, 9];
assert_eq!(Solution::find_substring(s, words), res);
let s = "wordgoodgoodgoodbestword".to_string();
let words = vec_string!["word", "good", "best", "word"];
let res: Vec<i32> = vec![];
assert_eq!(Solution::find_substring(s, words), res);
let s = "wordgoodgoodgoodbestword".to_string();
let words = vec_string!["word", "good", "best", "good"];
let res = vec![8];
assert_eq!(Solution::find_substring(s, words), res);
}