Backspace String Compare
Given two strings containing backspace characters, compare the final strings after applying the backspace operations.
Constraints:
- 1 <= s.length, t.length <= 200
- s and t only contain lowercase letters and '#' characters.
Examples:
Input: "ab#c","ad#c"
Output: true
Explanation: Applying the backspace operations, we get "ac" for both strings.
Solutions
Two-Pointer Approach
Time: O(n + m)Space: O(n + m)
We use a two-pointer approach to build the final strings after applying the backspace operations. We iterate through each string, and whenever we encounter a '#', we remove the last character from the string if it's not empty.
function backspaceCompare(s, t) {
return build(s) === build(t);
}
function build(s) {
let stack = [];
for (let i = 0; i < s.length; i++) {
if (s[i] !== '#') {
stack.push(s[i]);
} else if (stack.length > 0) {
stack.pop();
}
}
return stack.join('');
}
Follow-up:
How would you optimize the solution if the input strings are very large?
