Backspace String Compare Easy 0 attempts
LeetCode ↗

Backspace String Compare

Easy Stack&Queue LeetCode

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Example: s = "ab#c", t = "ad#c" → Output: true (both become "ac")

Sample Input
—
Sample Output
—
Constraints
  • 1 <= s.length, t.length <= 200
  • s and t contain lowercase letters and #
Test Cases
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.

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