diff options
author | Vincent Ambo <mail@tazj.in> | 2021-12-13T22·51+0300 |
---|---|---|
committer | Vincent Ambo <mail@tazj.in> | 2021-12-13T23·15+0300 |
commit | 019f8fd2113df4c5247c3969c60fd4f0e08f91f7 (patch) | |
tree | 76a857f61aa88f62a30e854651e8439db77fd0ea /users/wpcarro/scratch/data_structures_and_algorithms/norman.py | |
parent | 464bbcb15c09813172c79820bcf526bb10cf4208 (diff) | |
parent | 6123e976928ca3d8d93f0b2006b10b5f659eb74d (diff) |
subtree(users/wpcarro): docking briefcase at '24f5a642' r/3226
git-subtree-dir: users/wpcarro git-subtree-mainline: 464bbcb15c09813172c79820bcf526bb10cf4208 git-subtree-split: 24f5a642af3aa1627bbff977f0a101907a02c69f Change-Id: I6105b3762b79126b3488359c95978cadb3efa789
Diffstat (limited to 'users/wpcarro/scratch/data_structures_and_algorithms/norman.py')
-rw-r--r-- | users/wpcarro/scratch/data_structures_and_algorithms/norman.py | 78 |
1 files changed, 78 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/norman.py b/users/wpcarro/scratch/data_structures_and_algorithms/norman.py new file mode 100644 index 000000000000..379ba92abba8 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/norman.py @@ -0,0 +1,78 @@ + + + +# Write a function with the following type signature:L +# equal? :: String -> String -> Bool +# +# Determine equality between two inputs with backspace characters encoded as +# "<". + +################################################################################ +# Solution 1 +################################################################################ + +# from collections import deque + +# def equal(a, b): +# sa = deque() +# sb = deque() + +# for c in a: +# if c == '<': +# sa.pop() +# else: +# sa.append(c) + +# for c in b: +# if c == '<': +# sb.pop() +# else: +# sb.append(c) + +# return sa == sb + +################################################################################ +# Solution 2 +################################################################################ + +def handle_dels(num_dels, i, xs): + if i < 0: + return -1 + + while xs[i] == '<': + num_dels += 1 + i -= 1 + + while num_dels > 0 and xs[i] != '<': + num_dels -= 1 + i -= 1 + + if xs[i] == '<': + return handle_dels(num_dels, i, xs) + else: + return i + +def update_index(i, xs): + # TODO: Indexing into non-available parts of a string. + if xs[i] != '<' and xs[i - 1] != '<': + return i - 1 + + elif xs[i - 1] == '<': + return handle_dels(0, i - 1, xs) + +def equal(a, b): + ia = len(a) - 1 + ib = len(b) - 1 + + while ia >= 0 and ib >= 0: + if a[ia] != b[ib]: + return False + ia = update_index(ia, a) + ib = update_index(ib, b) + + if ia != 0: + return update_index(ia, a) <= -1 + if ib != 0: + return update_index(ib, b) <= -1 + + return True |