Two-Array.py

# Python program to find minimum number
# of operations to convert s1 to s2

# Function to find the minimum number 
# of operations to convert s1 to s2
def editDistance(s1, s2):
    m = len(s1)
    n = len(s2)

    # prev stores results for (i-1) th row
    # and curr for i-th row
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    # For 0-th row
    for j in range(n + 1):
        prev[j] = j

    # Rest of the rows
    for i in range(1, m + 1):
        curr[0] = i  # j = 0
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(curr[j - 1], prev[j], prev[j - 1])
        prev = curr[:]
    
    return prev[n]

if __name__ == "__main__":
    s1 = "abcd"
    s2 = "bcfe"

    print(editDistance(s1, s2))