Function leetcode_for_rust::cd0844_backspace_string_compare::backspace_compare

pub fn backspace_compare(s: String, t: String) -> bool

Solutions

Approach 1: Build String

• Time complexity: O(n)

• Space complexity: O(n)

• Runtime: 0ms

Memory: 2.4MB

impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        Self::build(s) == Self::build(t)
    }

    pub fn build(s: String) -> Vec<char> {
        let mut stack = vec![];
        for ch in s.chars() {
            if ch != '#' {
                stack.push(ch);
            } else {
                stack.pop();
            }
        }
        stack
    }
}

Approach 2: Two Pointer

• Time complexity: O(n)

• Space complexity: O(1)

• Runtime: 0ms

Memory: 2.3MB

impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        let s_bytes = s.as_bytes();
        let t_bytes = t.as_bytes();
        let mut i = s_bytes.len();
        let mut j = t_bytes.len();
        let mut skip = 0;

        loop {
            while i > 0 {
                if s_bytes[i-1] == b'#' {
                    skip += 1;
                } else if skip > 0 {
                    skip -= 1;
                } else {
                    break;
                }
                i -= 1;
            }

            while j > 0 {
                if t_bytes[j-1] == b'#' {
                    skip += 1;
                } else if skip > 0 {
                    skip -= 1;
                } else {
                    break;
                }
                j -= 1;
            }

            if i > 0 && j > 0 && s_bytes[i-1] == t_bytes[j-1] {
                i -= 1;
                j -= 1;
            } else {
                return i == 0 && j == 0 // only success when both totally consumed!
            }
        }
    }
}