codingpineapple

Posted on

# LeetCode 844. 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".
``````

### Solution:

Time complexity : O(n)

``````// In this solution we use an array like a stack
// to create 2 new strings from the inputs
// Then we check if they are equal
const backspaceCompare = (S, T) => buildString(S) === buildString(T);
// Helper function
function buildString(S) {
// Data structure that we will use to create the compare strings
const stack = [];
for (const c of S) {
// Add letter to the stack if it is not '#'
if (c != '#')
stack.push(c);
// Remove the most recently added letter if we encounter '#'
// and the stack is not empty
else if (stack.length!==0) {
stack.pop();
}
}
// Convert array to an string
return stack.join('');
}
``````