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)