3 ms·
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 pro
by the-smug-one 5y ago
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!
- thorwwaskeas 5y agofrom 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))