844. Backspace String Compare

Solution

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    let i = s.length - 1;
    let j = t.length - 1;
    let skipS = 0;
    let skipT = 0;
    
    // Loop from back of the strings and count '#'
    // so we can skip the correct number of chars
    while(i >= 0 || j >= 0) {
        while (i >= 0) {
            if (s[i] === '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break
            }
        }
        while (j >= 0) {
            if (t[j] === '#') {
                skipT++;
                j--;
            } else if (skipT > 0) {
                skipT--;
                j--;
            } else {
                break
            }
        }
        
        // Chars are different
        if (i >= 0 && j >= 0 && s[i] !== t[j]) {
            return false;
        }
        
        // Compare char with nothing
        if ((i >= 0) !== (j >= 0)) {
            return false;
        }
        
        i--;
        j--;
    }
    
    return true;
};

Complexity

  • Time Complexity: O(N+M), where N and M are the lengths of s and t.
  • Space Complexity: O(1).

All Solutions