Find And Replace in String LeetCode solution in Rust

1
use std::boxed::Box;
2

3
impl Solution {
4
  pub fn find_replace_string(
5
    s: String,
6
    indices: Vec<i32>,
7
    sources: Vec<String>,
8
    targets: Vec<String>,
9
  ) -> String {
10
    let s: Vec<char> = s.chars().collect();
11

12
    let mut idxs: Vec<(usize, usize, usize)> = indices
13
      .into_iter()
14
      .enumerate()
15
      .zip(sources.into_iter())
16
      .map(|((i, idx), src)| (i, idx as usize, src))
17
      .filter(|(_, idx, src)| {
18
        (s.len() - *idx) >= src.len() && // First make sure that src does not overflow the string as it is a less expensive preliminary check
19
            s.iter().skip(*idx) // Next we lazily check whether s[idx..] has src as its prefix
20
            .zip(src.chars()).all(|(&ch, src_ch)| src_ch == ch)
21
      })
22
      .map(|(i, idx, src)| {
23
        (i, idx, src.len()) // if so we keep track of the src length and the index from which we performed prefix matching
24
      })
25
      .collect();
26

27
    idxs.sort_by_key(|&(i, idx, lsrc)| idx); // we sort by index and we go from left to right
28

29
    let start: Box<dyn Iterator<Item = char>> = Box::new(std::iter::empty()); // we build our iterator using dynamic dispatch starting from an empty iterator
30

31
    let (it, last_idx) = idxs
32
      .into_iter()
33
      .fold((start, 0), |(iter_acc, s_next), (i, idx, lsrc)| {
34
        (
35
          Box::new(
36
            iter_acc
37
              .chain(s[s_next..idx].iter().cloned()) // we accumulate the original characters in s from s_next..idx
38
              .chain(targets[i].chars()),
39
          ), // we then need to accumulate the targets[i] characters
40
          idx + lsrc, // the next index to start replacing characters of s from would be idx+lsrc, which is the length of sources[i]
41
        )
42
      });
43

44
    let it = if last_idx < s.len() {
45
      Box::new(it.chain(s[last_idx..].iter().cloned())) // finally if we have some remaining characters in s then we accumulate those as well
46
    } else {
47
      it
48
    };
49

50
    it.collect() // finally we collect all the lazily accumulated iterators to form our result
51
  }
52
}