Backspace String Compare
Description
Given two strings S
and T
, return 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 = "#a#c" Output: true Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b".
Note:
1 <= S.length <= 200
1 <= T.length <= 200
S
andT
only contain lowercase letters and'#'
characters.
Follow up:
- Can you solve it in
O(N)
time andO(1)
space?
Solution(javascript)
/**
* @param {string} S
* @param {string} T
* @return {boolean}
*/
var backspaceCompare = function(S, T) {
let i = S.length - 1
let j = T.length -1
let count1 = 0
let count2 = 0
while(i >=0 || j >=0) {
while(S[i] === "#" || count1>0) {
if(S[i] === "#") {
count1 += 1
} else {
count1 -= 1
}
i--
}
while(T[j] === "#" || count2>0) {
if(T[j] === "#") {
count2 += 1
} else {
count2 -= 1
}
j--
}
if(S[i] !== T[j]) {
return false
}
i--
j--
}
return true
};