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
andt
only contain lowercase letters and'#'
characters.
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:
- Time complexity : O(n).
- Space complexity : O(1).