844. Backspace String Compare (Python)

Related Topic

Stack.

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.

Sample I/O

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. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and ‘#’ characters.

Methodology

Create two stacks one is for s and the other is for t. Iterate the string S, if meet ‘#’ and stack is not empty then we pop s_stack. Otherwise append the character to s_stack and character can not be ‘#’. The operation for string T is same. Finally we compare two stacks. If they are same return true else return false

    def backspaceCompare(self, S: str, T: str) -> bool:
        s_stack = []
        t_stack = []
        for s in S:
            if s == '#' and s_stack:
                s_stack.pop()
                continue
            if s != '#': s_stack.append(s)
        for t in T:
            if t == '#' and t_stack:
                t_stack.pop()
                continue
            if t != '#': t_stack.append(t)
        return s_stack == t_stack

BigO

We iterate the both string once the time complexity is O(N+M) where N and M is the length for string S ans string T.