import java.util.*;

class TUF {
    // Function to calculate the minimum edit distance between two strings
    static int editDistanceUtil(String S1, String S2, int i, int j, int[][] dp) {
        // Base cases
        if (i < 0)
            return j + 1;
        if (j < 0)
            return i + 1;

        // If the result is already computed, return it
        if (dp[i][j] != -1)
            return dp[i][j];

        // If the characters at the current positions match, no edit is needed
        if (S1.charAt(i) == S2.charAt(j))
            return dp[i][j] = editDistanceUtil(S1, S2, i - 1, j - 1, dp);

        // Minimum of three choices:
        // 1. Replace the character in S1 with the character in S2.
        // 2. Delete the character in S1.
        // 3. Insert the character from S2 into S1.
        else
            return dp[i][j] = 1 + Math.min(editDistanceUtil(S1, S2, i - 1, j - 1, dp),
                    Math.min(editDistanceUtil(S1, S2, i - 1, j, dp), editDistanceUtil(S1, S2, i, j - 1, dp)));
    }

    static int editDistance(String S1, String S2) {
        int n = S1.length();
        int m = S2.length();

        int[][] dp = new int[n][m];
        for (int row[] : dp)
            Arrays.fill(row, -1);

        // Call the recursive helper function
        return editDistanceUtil(S1, S2, n - 1, m - 1, dp);
    }

    public static void main(String args[]) {
        String s1 = "horse";
        String s2 = "ros";

        System.out.println("The minimum number of operations required is: " +
                editDistance(s1, s2));
    }
}

123456789101112131415161718192021222324252627282930313233343536373839404142434445

def editDistanceUtil(S1, S2, i, j, dp):
    # Base cases
    if i < 0:
        return j + 1
    if j < 0:
        return i + 1

    # If the result for this subproblem is already computed, return it
    if dp[i][j] != -1:
        return dp[i][j]

    # If the characters at the current positions match, no operation is needed
    if S1[i] == S2[j]:
        dp[i][j] = editDistanceUtil(S1, S2, i - 1, j - 1, dp)
    else:
        # Calculate the minimum of three choices:
        # 1. Replace the current character (diagonal move)
        # 2. Insert a character into S1 (move up)
        # 3. Delete a character from S1 (move left)
        dp[i][j] = 1 + min(
            editDistanceUtil(S1, S2, i - 1, j - 1, dp),
            min(editDistanceUtil(S1, S2, i - 1, j, dp), editDistanceUtil(S1, S2, i, j - 1, dp))
        )

    return dp[i][j]

def editDistance(S1, S2):
    n = len(S1)
    m = len(S2)

    # Initialize a 2D DP array with -1 values
    dp = [[-1 for _ in range(m)] for _ in range(n)]

    # Calculate and return the edit distance
    return editDistanceUtil(S1, S2, n - 1, m - 1, dp)

def main():
    s1 = "horse"
    s2 = "ros"

    # Calculate and print the minimum number of operations required
    print("The minimum number of operations required is:", editDistance(s1, s2))

if __name__ == "__main__":
    main()