deleteDistance.py

def deletion_distance(str1, str2):
    @lru_cache(None)
    def recursiveHelper(str3, str4):
        if not str4 or not str3: return ''
        idx = str3.find(str4[0])
        store = (str4[0] + recursiveHelper(str3[idx+1:], str4[1:])) if idx != -1 else ''
        return store if idx == 0 else max(store, recursiveHelper(str3, str4[1:]), key=len)
        
    return len(str1) + len(str2) - 2*len(recursiveHelper(str1, str2))