README.md

844. Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

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.

Follow up:

• Can you solve it in O(N) time and O(1) space?

Solutions (Python)

1. Stack

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        stack_s = []
        stack_t = []

        for ch in S:
            if ch != '#':
                stack_s.append(ch)
            elif stack_s:
                stack_s.pop()
        for ch in T:
            if ch != '#':
                stack_t.append(ch)
            elif stack_t:
                stack_t.pop()

        return stack_s == stack_t

2. Two Pointers

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        i, j = len(S) - 1, len(T) - 1

        while i >= 0 or j >= 0:
            cnt = 0
            while i >= 0 and (S[i] == '#' or cnt > 0):
                cnt += 1 if S[i] == '#' else -1
                i -= 1

            cnt = 0
            while j >= 0 and (T[j] == '#' or cnt > 0):
                cnt += 1 if T[j] == '#' else -1
                j -= 1

            if (i < 0) != (j < 0) or (i + j >= 0 and S[i] != T[j]):
                return False

            i -= 1
            j -= 1

        return True