Untitled

mail@pastecode.io avatar
unknown
rust
a month ago
2.2 kB
3
Indexable
Never
impl Solution {
    pub fn find_substring(s: String, wrds: Vec<String>) -> Vec<i32> {
        use std::collections::HashMap;

        let mut ret = vec![];
        let wrd_len = wrds[0].len();
        let total_len = wrd_len * wrds.len();

        // Check for minimum edge condition.
        // The target string length must be
        // equal to or great than the permutation length.
        if s.len() < total_len {
            return ret;
        }

        // Calculate expected word frequencies.
        let mut exp_cnts: HashMap<&str, i32> = HashMap::new();
        for wrd in &wrds {
            *exp_cnts.entry(wrd.as_str()).or_insert(0) += 1;
        }

        // Loop through length of word.
        // Substring maybe offset by some characters.
        for idx_chr in 0..wrd_len {
            let mut wnd_cnts: HashMap<&str, i32> = HashMap::new();
            let mut prm_cnt: usize = 0;
            let mut lft = idx_chr;

            for rht in (idx_chr..=s.len() - wrd_len).step_by(wrd_len) {
                // Look for a word in the target substring.
                let rht_wrd = &s[rht..rht + wrd_len];
                
                if let Some(&exp_cnt) = exp_cnts.get(rht_wrd) {
                    // Found a word.
                    // Increment the observed word count.
                    *wnd_cnts.entry(rht_wrd).or_insert(0) += 1;
                    prm_cnt += 1;

                    // Check whether to shrink the window on the left side.
                    while wnd_cnts[rht_wrd] > exp_cnt {
                        let lft_wrd = &s[lft..lft + wrd_len];
                        *wnd_cnts.get_mut(lft_wrd).unwrap() -= 1;
                        lft += wrd_len;
                        prm_cnt -= 1;
                    }

                    // Check whether we've found a solution.
                    if prm_cnt == wrds.len() {
                        ret.push(lft as i32);
                    }
                } else {
                    // No word found.
                    // Reset tracking variables.
                    wnd_cnts.clear();
                    prm_cnt = 0;
                    lft = rht + wrd_len;
                }
            }
        }

        ret
    }
}
Leave a Comment