Backspace String Compare Easy 0 attempts
LeetCode ↗

Backspace String Compare

Easy Stack&Queue LeetCode

You're given two strings s and t made of lowercase letters and the # character, where # acts as a backspace key that deletes the previous character as each string is typed into an empty text editor. Simulate the typing and return whether the two final results match.

Input Format
Implement backspaceCompare(s, t). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
s = "ab#c"
t = "ad#c"
Output
true

Example 2

Input
s = "ab##"
t = "c#d#"
Output
true

Example 3

Input
s = "a#c"
t = "b"
Output
false
Constraints
  • 1 <= s.length, t.length <= 200
  • s and t contain lowercase letters and #
Test Cases (3)
Case 1
Args: ["ab#c","ad#c"] Expected: true
Case 2
Args: ["ab##","c#d#"] Expected: true
Case 3
Args: ["a#c","b"] Expected: false
Topics
Stack&Queue

Two Pointer from End

Process both strings from right to left, skipping characters after backspaces.

javascript
function backspaceCompare(s, t) {
  let i = s.length - 1, j = t.length - 1;
  while (i >= 0 || j >= 0) {
    let skip = 0;
    while (i >= 0 && (s[i] === '#' || skip > 0)) { skip += s[i] === '#' ? 1 : -1; i--; }
    skip = 0;
    while (j >= 0 && (t[j] === '#' || skip > 0)) { skip += t[j] === '#' ? 1 : -1; j--; }
    if (i >= 0 && j >= 0 && s[i] !== t[j]) return false;
    if ((i >= 0) !== (j >= 0)) return false;
    i--; j--;
  }
  return true;
}

Time: O(m + n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript