levenshtein_memoization_Improved.py

# I added a 'memo' dictionary as an optional argument to store previously computed results.
def levenshtein_distance_memo(s1, s2, memo=None):
    # I initialized the memo dictionary on the first call so the cache is carried through recursion.
    if memo is None:
        memo = {}
        
    # I created a unique key based on the current state (lengths of strings).
    # I used lengths as keys instead of the strings themselves. 
    key = (len(s1), len(s2))
    
    # I added a check to see if I have already solved this sub-problem. If so, I return the stored value to avoid redundant calculations.
    if key in memo:
        return memo[key]
    
    # I kept the original logic for Base Case 1: If s1 is empty, distance is length of s2 [cite: 39-40]
    if len(s1) == 0:
        return len(s2)
        
    # I kept the original logic for Base Case 2: If s2 is empty, distance is length of s1 [cite: 41-42]
    if len(s2) == 0:
        return len(s1)
        
    # I kept the original cost check: 0 if characters match, 1 otherwise [cite: 43-46]
    if s1[-1] == s2[-1]:
        cost = 0
    else:
        cost = 1
        
    # For the recursive step, I updated the original minimum calculation to pass my 'memo' dictionary to all recursive calls so they share the cache.
    res = min(
        levenshtein_distance_memo(s1[:-1], s2, memo) + 1,      # Deletion
        levenshtein_distance_memo(s1, s2[:-1], memo) + 1,      # Insertion
        levenshtein_distance_memo(s1[:-1], s2[:-1], memo) + cost # Substitution
    )
    
    # Finally, instead of returning directly, I saved the computed result in my memo dictionary before returning it.
    memo[key] = res
    return res

my_ku_id = "K2358622"
staff_id = "KU13043"

distance = levenshtein_distance_memo(my_ku_id, staff_id)

print(f"Levenshtein distance between {my_ku_id} and {staff_id} is: {distance}")