Almost ASCII Deletion Distance

almost-ascii-deletion-distance.py

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

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