844. Backspace String Compare Easy

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".

Approach

Input: Two strings s and t

Output: Determine whether the final content is identical after they are typed into empty text editors (return true or false)

This problem belongs to the Basic Stack category.

We can utilize the "Last In, First Out" feature of stacks to simulate the typing process:

Traverse the string, pushing normal characters into the stack;

When encountering a # (Backspace), pop the top element from the stack (if any);

Finally, compare whether the resulting character sequences constructed by the two stacks are identical.

Implementation

python

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        # Define a common function to process the string into the backspaced result
        def build(string):
            stack = []
            for c in string:
                if c == '#':
                    if stack:
                        stack.pop()  # Pop the top character when a backspace is encountered
                else:
                    stack.append(c)  # Push normal characters onto the stack
            return stack

        # Process both strings and compare the final results
        return build(s) == build(t)

javascript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
const backspaceCompare = function(s, t) {
    function build(str) {
        const stack = [];
        for (let c of str) {
            if (c == '#') {
                if (stack.length) {
                    stack.pop()
                }
            } else {
                stack.push(c);
            }
        }

        return stack.join('');
    }

    return build(s) == build(t);
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

844. Backspace String Compare (English)

844. 比较含退格的字符串 (Chinese)