[−][src]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! } } } }