Backspace String Compare

Problem

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

Note that after backspacing an empty text, the text will continue empty.

 

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 "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

 

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    const sc = [];
    const tc = [];
    const n = Math.max(s.length, t.length);

    // build the two strings
    for (let i = 0; i < n; i++) {
        if (s[i] === "#") {
            sc.pop();
        } else if (s[i]) {
            sc.push(s[i]);
        }

        if (t[i] === "#") {
            tc.pop();
        } else if (t[i]) {
            tc.push(t[i]);
        }
    }

    return sc.join("") === tc.join("");
};

Build the two strings using a stack and compare if they are equal.

Follow-up

Can you solve it in O(n) time and O(1) space?

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    let si = s.length - 1;
    let ti = t.length - 1;

    // get letters in s and t in reverse direction
    while (si >= 0 || ti >= 0) {
        // get next letter in s
        let skipS = 0;
        while (si >= 0) {
            if (s[si] === "#") {
                skipS++;
                si--;
            } else if (skipS > 0) {
                skipS--;
                si--;
            } else {
                break;
            }
        }
        const sc = s[si];

        // get next letter in t
        let skipT = 0;
        while (ti >= 0) {
            if (t[ti] === "#") {
                skipT++;
                ti--;
            } else if (skipT > 0) {
                skipT--;
                ti--;
            } else {
                break;
            }
        }
        const tc = t[ti];

        // compare if next letter in t same as next letter in s
        if (sc !== tc) {
            return false;
        }
        si--;
        ti--;
    }
    return true;
};

We will implement a two pointers solution. Notice that if we iterate forwards, we don't know if the current letter we're on will actually be in the built string (ie. backspaces after could remove it). However, this is not an issue if we iterate backwards, since we can keep track of how many backspaces there are (thus knowing how many characters to ignore). Using this observation, we can get the letters of the built string one character at a time for s and t starting from the end, and compare whether they are the same. If any one character is different, then s and t after being built must also be different.