METHOD = '''
- if first char is equal just consider the problem with first chars ignored
- if the first char are not equal
    - either it has to be deleted
        - recursively solve by ignoring first char of first str
    - or swapped
        - recursively solve by ignoring first char of both str
    - or a char must be inserted before it
        - recursively solve by ignoring first char of second str
- Base would encountered when one of any string is empty
    - We would simply return difference b/w length of remaining string and its current position
'''

# Recursive Solution
def min_steps_1(a: str, b: str, idx_a=0, idx_b=0) -> int:
    if idx_a == len(a):
        return len(b) - idx_b
    
    if idx_b == len(b):
        return len(a) - idx_a
        
    if a[idx_a] == b[idx_b]:
        return min_steps_1(a, b, idx_a + 1, idx_b + 1)
    
    deletion = min_steps_1(a, b, idx_a + 1, idx_b)
    swapping = min_steps_1(a, b, idx_a + 1, idx_b + 1)
    insertion = min_steps_1(a, b, idx_a, idx_b + 1)
    
    return 1 + min(deletion, swapping, insertion)

# Memoized Solution
def min_steps_2(a: str, b: str) -> int:
    memo = {}
    
    def recurse(idx_a=0, idx_b=0):
        key = (idx_a, idx_b)
        if key in memo:
            return memo[key]
        
        if idx_a == len(a):
            memo[key] = len(b) - idx_b
            
        elif idx_b == len(b):
            memo[key] = len(a) - idx_a
        
        elif a[idx_a] == b[idx_b]:
            memo[key] = recurse(idx_a + 1, idx_b + 1)
        
        else:
            delete = recurse(idx_a + 1, idx_b)
            swap = recurse(idx_a + 1, idx_b + 1)
            insert = recurse(idx_a, idx_b + 1)
        
            memo[key] = 1 + min(delete, swap, insert)
        
        return memo[key]
    
    return recurse()

# Dynamic Solution
def min_steps_3(a: str, b: str) -> int:
    m, n = len(a), len(b)
    tab = [0] * max(m,n)
    
    i = 0
    while i < m and i < n:
        if a[i] == b[i]:
            tab[i] = tab[i-1]
        else:
            tab[i] = 1 + tab[i-1]
        i += 1
        
    while i < m or i < n:
        tab[i] = 1 + tab[i-1]
        i +=1
    return tab