Can this code be any simpler?

[Zetazzz]

Hi, I did a random leetcode question with Rust:

Given two strings S and T , return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c" Output: true Explanation : Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#" Output: true Explanation : Both S and T become "".

And my solution is:

struct Filter(u32);

impl Filter {
    fn new() -> Self {
        Filter(0)
    }

    fn filter(&mut self, c: &char) -> bool {
        if c == &'#' {
            self.0 += 1;
            false
        } else {
            if self.0 == 0 {
                true
            } else {
                self.0 -= 1;
                false
            }
        }
    }
}

fn backspace_compare(s: String, o: String) -> bool {
    let mut s_filter = Filter::new();
    let mut last_s_iter = s.chars().rev().filter(|c| s_filter.filter(c));

    let mut o_filter = Filter::new();
    let mut last_o_iter = o.chars().rev().filter(|c| o_filter.filter(c));

    loop {
        let last_s = last_s_iter.next();
        let last_o = last_o_iter.next();

        if last_s != last_o {
            return false;
        }

        if last_s.is_none() {
            break;
        }
    }
    return true;
}

The performance was good enough. But I'm wondering can these codes be simpler. Like using closure or using Iterator instead of the loop. I tried to use closure instead of the struct, but failed because of the lifetime:

fn get_filter() -> impl FnMut(&char)->bool{

    let mut bs_counter=0; //bs_counter not live long enough. And I don't know how to add lifetime to this...

    |c|{
        if c == &'#' {
            bs_counter += 1;
            false
        } else {
            if bs_counter == 0 {
                true
            } else {
                bs_counter -= 1;
                false
            }
        }
    }
}

Just want to know the best practice of these, thank you very much!

[ZiCog]

Is there some particular reason not to do it the most obvious way?

fn edit (input: &str) -> String {
    let mut output: String = String::from("");

    for c in input.chars() {
        if c == '#' {
            output.pop();
        } else {
            output.push(c);
        }
    }
    output
}

fn backspace_compare(s: &str, o: &str) -> bool {
    edit(s) == edit(o)
}

I'm not sure why we might need structs and lambdas and all that unnecessary stuff.

[Zetazzz]

For "a##b" and "a##c", you don't have to iterate whole both to tell the difference, consider if the string is too long, and a stack like solution cost extra memory(O(n), I believe it's O(1) for iter solution). But anyway, the solution is not important, I just want to know is there a decent way to return a closure with state,
(I just realize my way of questioning was not good. I will have other topics on more specific questions.) Thank you very much anyway.

[Zetazzz]

I figured out a simpler way:

fn scan_filter(bs_count: &mut u32, c: char) -> Option<Option<char>> {
    if c == '#' {
        *bs_count += 1;
        Some(None)
    } else if bs_count != &0 {
        *bs_count -= 1;
        Some(None)
    } else {
        Some(Some(c))
    }
}

fn backspace_compare(s: String, o: String) -> bool {
    let mut last_s_iter = s.chars().rev().scan(0u32, scan_filter).filter_map(|c| c);
    let mut last_o_iter = o.chars().rev().scan(0u32, scan_filter).filter_map(|c| c);

    loop {
        let last_s = last_s_iter.next();
        let last_o = last_o_iter.next();

        if last_s != last_o {
            return false;
        }

        if last_s.is_none() {
            break;
        }
    }
    return true;
}

[marcianx]

Very nice! You can use Iterator::eq to shorten your O(1)-space solution:

fn backspace_equivalent(s: &str, o: &str) -> bool {
    let last_s_iter = s.chars().rev().scan(0u32, scan_filter).filter_map(|c| c);
    let last_o_iter = o.chars().rev().scan(0u32, scan_filter).filter_map(|c| c);
    last_s_iter.eq(last_o_iter)
}

(Playground)
Also please note that I also replaced the String arguments with &str as there's no need to consume the string.