Skip to content

Instantly share code, notes, and snippets.

@fish2000
Created March 14, 2017 17:56
Show Gist options
  • Save fish2000/ea7e0822a5b45fc1a64ac50c16ec7b11 to your computer and use it in GitHub Desktop.
Save fish2000/ea7e0822a5b45fc1a64ac50c16ec7b11 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
@tisaconundrum2
Copy link

tisaconundrum2 commented May 24, 2017

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