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.

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

Follow up:

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

Source: leetcode | Difficulty: EASY
Tags: String algorithms

Data structures

Amortized analysis

Starter code: class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        

Solutions:
class Solution:

	def backspaceCompare(self, S1, S2):
		i1 = len(S1) - 1
		i2 = len(S2) - 1
		while i1 >= 0 or i2 >= 0:
			c1 = ''
			c2 = ''
			if i1 >= 0:
				(c1, i1) = self.getChar(S1, i1)
			if i2 >= 0:
				(c2, i2) = self.getChar(S2, i2)
			if c1 != c2:
				return False
		return True

	def getChar(self, s, i):
		char = ''
		count = 0
		while i >= 0 and (not char):
			if s[i] == '#':
				count += 1
			elif count == 0:
				char = s[i]
			else:
				count -= 1
			i -= 1
		return (char, i)


class Solution:

	def backspaceCompare(self, S: str, T: str) -> bool:

		def test(s):
			stack = []
			for l in s:
				if l == '#':
					if len(stack) != 0:
						stack.pop()
				else:
					stack.append(l)
			return ''.join(stack)
		return test(S) == test(T)


class Solution:

	def backspaceCompare(self, S: str, T: str) -> bool:
		(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)


class Solution:

	def backspaceCompare(self, S: str, T: str) -> bool:
		i = len(S) - 1
		j = len(T) - 1
		skip_S = 0
		skip_T = 0
		while i >= 0 or j >= 0:
			while i >= 0 and (S[i] == '#' or skip_S > 0):
				if S[i] == '#':
					skip_S += 1
				else:
					skip_S -= 1
				i -= 1
			while j >= 0 and (T[j] == '#' or skip_T > 0):
				if T[j] == '#':
					skip_T += 1
				else:
					skip_T -= 1
				j -= 1
			if i < 0 and j < 0:
				return True
			elif i >= 0 and j >= 0:
				if S[i] == T[j]:
					i -= 1
					j -= 1
				else:
					return False
			elif i >= 0 or j >= 0:
				return False
		return True


class Solution:

	def backspaceCompare(self, S: str, T: str) -> bool:
		s = []
		for i in S:
			if i == '#':
				if s:
					s.pop()
			else:
				s.append(i)
		t = []
		for i in T:
			if i == '#':
				if t:
					t.pop()
			else:
				t.append(i)
		if s == t:
			return True
		return False


class Solution:

	def backspaceCompare(self, S: str, T: str) -> bool:

		def helper(S):
			r = ''
			erase = 0
			for s in S[-1::-1]:
				if s == '#':
					erase += 1
				elif s != '#' and erase == 0:
					r = s + r
				elif s != '#' and erase >= 1:
					erase -= 1
			return r
		return helper(S) == helper(T)