using System;

public class Program

{

      //DynamicProgramming

  public static int DeletionDistance(string str1, string str2)

  {

    if (str1.Length == 0 && str2.Length != 0){

      return str2.Length;

    }

    if (str2.Length == 0 && str1.Length != 0){

      return str1.Length;

    }

    if (str1 == str2) return 0;

​

    var matrix = new int[str1.Length+1, str2.Length+1];

    for(var i=0; i<str1.Length+1; i++){

      matrix[i,0] = i;

    }

    for(var j=0; j<str2.Length+1; j++){

      matrix[0,j] = j;

    }

    for(var i=1; i<str1.Length+1; i++){

      for(var j=1; j<str2.Length+1; j++){

        if (str1[i-1] == str2[j-1]){

          matrix[i,j] = matrix[i-1,j-1];

        }

        else {

          matrix[i,j] = Math.Min(matrix[i-1,j],matrix[i,j-1]) + 1;

        }

      }

    }

    return matrix[str1.Length,str2.Length];

  }

    public static void Main()

    {

        Console.WriteLine(DeletionDistance("abc","abcd")); //1

        Console.WriteLine(DeletionDistance("dogle","frog")); //5

    }

}