dbackspace.py

# using backtracking
def dbackspace(s, t) -> bool:
	picked = []
	n = len(s)

	def f(i) -> bool:
		if i >= n:
			return "".join(map(lambda j: s[j], picked)) == t

		picked.append(i)
		if f(i+1):
			return True
		if picked:
			picked.pop()
		if picked:
			picked.pop()
		return f(i+1)
	
	return f(0)

# using recursion+memoization
from functools import lru_cache
def dbackspace(s, t) -> bool:
	@lru_cache()
	def f(i,j) -> bool:
		if i >= len(s) and j >= len(t):
			return True
		elif i >= len(s) or j >= len(t):
			return False

		if s[i] == t[j] and f(i+1,j+1):
			return True
		return f(i+1, max(0, j-1))

	return f(0,0)

# bottom-up dynamic programming
def dbackspace(s,t) -> bool:
	m,n = len(s), len(t)
	dp = [[False for _ in range(n+1)] for _ in range(m+1)]
	dp[-1][-1] = True
	for i in range(m-1, -1, -1):
		for j in range(n):
			if s[i] == t[j] and dp[i+1][j+1]:
				dp[i][j] = True
			dp[i][j] |= dp[i+1][max(0, j-1)]
	return dp[0][0]

# move right to left, much easier: inspired by AlphaCode output
# https://deepmind.com/blog/article/Competitive-programming-with-AlphaCode
def dbackspace(s,t) -> bool:
	m,n = len(s), len(t)
	i,j = m-1, n-1
	while i >= 0 and j >= 0:
		if s[i] == t[j]:
			i -= 1
			j -= 1
		elif i >= 2:
			i -= 2
		else:
			i -= 1
	return j < 0

assert dbackspace("", "") == True
assert dbackspace("ababa", "ba") == True
assert dbackspace("ababa", "bb") == False
assert dbackspace("aaa", "aaaa") == False
assert dbackspace("aababa", "ababa") == True