Untitled

mail@pastecode.io avatar
unknown
rust
a month ago
2.4 kB
2
Indexable
Never
use std::collections::{HashMap, VecDeque};

impl Solution {
    pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
        let (l, words_l, word_l) = (s.len(), words.len(), words[0].len());
        if l < words_l * word_l {
            return vec![]
        }
        let s = s + &" ".repeat(word_l - l % word_l);
        let mut res = vec![];
        for i in 0..words[0].len() {
            let phantom_s = s.chars().skip(i).collect::<String>() + &" ".repeat(i);
            res.extend(
                Self::_find_substring(phantom_s, words.clone())
                    .into_iter()
                    .map(|x| x + i as i32)
                    .collect::<Vec<i32>>(),
            );
        }
        res
    }
    fn _find_substring(s: String, words: Vec<String>) -> Vec<i32> {
        let (word_len, substring_len) = (words[0].len(), words.len());
        let words =
            words
                .into_iter()
                .fold(HashMap::new(), |mut acc: HashMap<String, i32>, word| {
                    *acc.entry(word).or_default() += 1;
                    acc
                });
        let mut window: VecDeque<i32> = VecDeque::new();
        let mut window_ctr: HashMap<String, i32> = HashMap::new();
        let (mut res, mut fast) = (vec![], 0);
        while fast < s.len() {
            let word = (s[fast..fast + word_len]).to_owned();
            if !words.contains_key(&word) {
                window.clear();
                window_ctr.clear();
                fast += word_len;
                continue;
            }
            while window_ctr.entry(word.clone()).or_default() == words.get(&word).unwrap() {
                let start_index = window.pop_front().unwrap() as usize;
                let start_word = (s[start_index..start_index + word_len]).to_owned();
                *window_ctr.entry(start_word).or_default() -= 1;
            }
            window.push_back(fast as i32);
            *window_ctr.entry(word.clone()).or_default() += 1;
            if window.len() == substring_len {
                let start_index = window.pop_front().unwrap() as usize;
                let start_word = (s[start_index..start_index + word_len]).to_owned();
                *window_ctr.entry(start_word).or_default() -= 1;
                res.push(start_index as i32);
            }
            fast += word_len;
        }
        res
    }
}
Leave a Comment