Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save AppMkrATL/52b02e9f2486a0c9aa45968b22797b80 to your computer and use it in GitHub Desktop.
Save AppMkrATL/52b02e9f2486a0c9aa45968b22797b80 to your computer and use it in GitHub Desktop.
Almost ASCII Deletion Distance
def ascii_deletion_distance(str1, str2):
from collections import defaultdict
histogram = defaultdict(int)
for ch in str1:
histogram[ch] += 1
for ch in str2:
histogram[ch] += 1
union = set(str1) | set(str2)
intersection = set(str1) & set(str2)
result = union - intersection
# values = [ord(ch) for ch in result]
out = 0
for ch in result:
out += (histogram[ch] * ord(ch))
return out
@AppMkrATL
Copy link
Author

AppMkrATL commented Sep 19, 2018

image

image

As we can see it doesn't hit all scenarios.
Here's my solution to the problem.

def ascii_deletion_distance(s1, s2):
list1 = compareLetters(s1, s2)
list2 = compareLetters(s2, s1)
return sum(list1+list2)

def stillLetters(s):
return len(s) > 0

def compareLetters(s1, s2):
count = 0
list = []
while stillLetters(s1) and stillLetters(s2):
for i in range(len(s1)):
for j in range(len(s2)):
if s1[0] == s2[j]:
s1 = s1[:0] + s1[1:]
s2 = s2[:j] + s2[j + 1:]
count += 1
break

    if not s1[:1] == "": list.append(ord(s1[:1]))
    s1 = s1[:0] + s1[1:]
return list

print(ascii_deletion_distance("at", "cat"))
print(ascii_deletion_distance("boat", "got"))
print(ascii_deletion_distance("thought", "sloughs"))

Output

==========

99

298

674

I know this is not the best solution, as it's possible to get this working in an O(n) case. But given the time I had to solve it... It was rushed.
The worst case is O(n^2), with a best case of O(n)

worst case
abcd
dcba

will take O(n^2)

best case
abcd
abcd

will take O(n

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment