844. Backspace String Compare

Difficulty:
Related Topics:
Similar Questions:

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:

  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) {
    var i = s.length - 1;
    var j = t.length - 1;
    while (i >= 0 || j >= 0) {
        i = findCharIndex(s, i);
        j = findCharIndex(t, j);
        if (s[i] !== t[j]) return false;
        i--;
        j--;
    }
    return true;
};

var findCharIndex = function(s, i) {
    var num = 0;
    while (num || s[i] === '#') {
        s[i] === '#' ? num++ : num--;
        i--;
    }
    return i;
}

Explain:

nope.

Complexity: