72. Edit Distance - 2019 practice

I always like to write C# solution by myself. No matter how good I can understand the dynamic programming, it is always good idea to spend 10 minutes to write a solution.

I thought that I can write a bug free code, but I came cross two bugs. One is missing one problem, I forgot to increment one in first writing and it is caught by online judge. Second one is to play with compiler, and understand the preference of operators.

Here is my discussion post for my last writing.

It is time for me to write a solution using C# and I like to make it bug free, and also it should take me less than 20 minutes.

I just reviewed my two past practice back in 2015 and 2017. To make myself a good problem solver on Edit Distance, I push myself to share and write down some comment first. I also have to learn how to write a C# solution. It does not matter how good I am in dynamic programming, the most important is to train myself to write a solution without any bug.

Here are highlights:

1. Base case is one of string is empty, or both string are empty;
2. Empty string is a choice, so distance matrix can be declared using two dimension array with plus one with length of word1 and word2;
3. Work on three subproblems, I came cross the run time error because I wrote
   var crossValue = cross + left == top? 0 : 1;
4. Extra on step 3, I extracted one statement called increment variable;
5. I forgot to increment one on left and top two subproblems case; It is caught by online judge.
6. Use Array.Min to avoid Math.Min API call. Code is simple to write.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _72_edit_distance
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// edit distance 72
        /// 2019 July 7
        /// 
        /// </summary>
        /// <param name="word1"></param>
        /// <param name="word2"></param>
        /// <returns></returns>
        public int MinDistance(string word1, string word2)
        {
            if (word1 == null || word2 == null)
                return 0;

            var length1 = word1.Length;
            var length2 = word2.Length;
            if (length1 == 0)
                return length2;
            if (length2 == 0)
                return length1;

            var distance = new int[length1 + 1, length2 + 1];

            // base case: 
            for (int column = 0; column < length2 + 1; column++)
            {
                distance[0, column] = column;
            }

            for (int row = 0; row < length1 + 1; row++)
            {
                distance[row, 0] = row;
            }

            // work on three subproblems - left, top, cross top-left
            for (int row = 1; row < length1 + 1; row++)
            {
                var left = word1[row - 1]; // first one is ""

                for (int col = 1; col < length2 + 1; col++)
                {
                    var top = word2[col - 1];

                    var leftValue = distance[row, col - 1];
                    var topValue = distance[row - 1, col];

                    var cross = distance[row - 1, col - 1];
                    var increment = left == top ? 0 : 1;  // caught by online judge, extract to one statement alone
                    var crossValue = cross + increment;

                    var numbers = new int[] { leftValue + 1, topValue + 1, crossValue };
                    distance[row, col] = numbers.Min();
                }
            }

            return distance[length1, length2];
        }
    }
}