Calculate minimum number of deletes needed for equalizing two strings.

min_deletes_to_equalize.py

#!/bin/python3
"""
Given two strings, s1 and s2, calculate the minimum number of deletions needed to make s1 == s2
For example: for the strings (AABAAB, ABAB) you need to delete two 'A's from the left string.

This is a variation of the longest subsequence problem.
"""

import os
import sys
import numpy as np

def num_deletes(s1, s2):
    """
    Given two strings, s1 and s2, return the number of deletes needed to make them equal.
    """
    matrix = np.ndarray((len(s2) + 1, len(s1) + 1), dtype=int)
    matrix[0, :] = list(range(len(s1) + 1)) # fill first row
    matrix[:, 0] = list(range(len(s2) + 1)) # fill first column

    for row in range(len(s2)):
        for col in range(len(s1)):
            c_s1 = s1[col]
            c_s2 = s2[row]

            if c_s1 == c_s2:
                matrix[row+1][col+1] = matrix[row][col]
            else:
                matrix[row+1][col+1] = min(matrix[row][col+1], matrix[row+1][col]) + 1

    for row in matrix:
        print(row)

    return matrix[len(s2)][len(s1)]


if __name__ == '__main__':
    fptr = sys.stdout

    s1 = input()
    s2 = input()

    result = num_deletes(s1, s2)

    fptr.write(str(result) + '\n')
    fptr.close()