I'm trying to solve this for fun, but I'm stuck! I've got a recursive definition that solves the problem by building a result string. I think it's a dynamic programming problem, but right now I can't see the shared sub-problems so :). Some real sour cherries being experienced from not getting this one!
from collections import defaultdict
def backspace(s1,s2):
h = defaultdict(lambda:0)
for x in s1:
h[x] = h[x] + 1
for x in s2:
h[x] = h[x] - 1
j = 0
maxj = len(s2) - 1
for x in s1:
if x != s2[j]:
h[x] -= 1
elif j < maxj:
j += 1
else:
break
return j == maxj and all(y >= 0 for y in h.values())
def random_backspace(s1):
res = []
for x in s1:
if randint(0,1) == 0:
res.append(x)
return "".join(res)
def backspaceTest(s1):
return all(backspace(s1,random_backspace(s1)) for _ in range(100))
