Problem statement

https://leetcode.com/problems/backspace-string-compare/

Solution

O(n + m) time and space solution is straightforward: use stack and imitate process.

If we want to do it in O(1) space, we need to go from the end of string, because if we go from the beginning we do not know in advance if symbol will be erased or not. Let i, j be indexes for the first and the second string and backS, backT be counter how many symbols we need to erase. We iterate over both strings until we need to remove symbols and then compare symbols.

Complexity

It is O(m + n) for time and O(1) for space.

Code

# borrowed code
class Solution:
    def backspaceCompare(self, S, T):
        i, j = len(S) - 1, len(T) - 1
        backS = backT = 0
        while True:
            while i >= 0 and (backS or S[i] == '#'):
                backS += 1 if S[i] == '#' else -1
                i -= 1
            while j >= 0 and (backT or T[j] == '#'):
                backT += 1 if T[j] == '#' else -1
                j -= 1
            if not (i >= 0 and j >= 0 and S[i] == T[j]):
                return i == j == -1
            i, j = i - 1, j - 1