Edit Distance

EditDistance

using System;

namespace EditDistance
{
    public class Program
    {
        
        const int SUBSTITUTION_COST = 1;
        const int INSERTION_COST = 2;
        const int DELETION_COST = 2;
        
        public static void Main(string[] args)
        {
            string fromString = "saturday";
            string toString = "sunday";
            
            Console.WriteLine("Recursive: Cost of converting {0} to {1} is {2}", 
                fromString, 
                toString, 
                GetEditCostRecursive(fromString, toString));
                
            Console.WriteLine("Iterative: Cost of converting {0} to {1} is {2}", 
                fromString, 
                toString, 
                GetEditDistanceIterative(fromString, toString));       
        }
        
        // Convert s1 to s2
        // Time complexity ~ O(3 ^ max(m, n)), not sure how to arrive at this
        // complexity
        public static int GetEditCostRecursive(string s1, string s2) {
            if (String.IsNullOrEmpty(s1) && String.IsNullOrEmpty(s2)) {
                return 0;
            }
            
            if (String.IsNullOrEmpty(s1)) {
                return s2.Length * INSERTION_COST;
            }
            
            if (String.IsNullOrEmpty(s2)) {
                return s1.Length * DELETION_COST;
            }
            
            if (s1[s1.Length - 1] == s2[s2.Length - 1]) {
                return GetEditCostRecursive(s1.Substring(0, s1.Length - 1), s2.Substring(0, s2.Length - 1));
            }
            
            int candidate1 = GetEditCostRecursive(s1.Substring(0, s1.Length - 1), s2.Substring(0, s2.Length - 1)) 
                + SUBSTITUTION_COST;
                
            int candidate2 = GetEditCostRecursive(s1, s2.Substring(0, s2.Length - 1)) + INSERTION_COST;
            
            int candidate3 = GetEditCostRecursive(s1.Substring(0, s1.Length - 1), s2) + DELETION_COST;
            
            int minCandidate = Math.Min(candidate1, candidate2);
            
            return Math.Min(minCandidate, candidate3);
        }
        
        // Time complexity: O(n ^ 2)
        // Space complexity: O(n ^ 2)
        public static int GetEditDistanceIterative(string s1, string s2) {
           	if (String.IsNullOrEmpty(s1) && String.IsNullOrEmpty(s2)) {
                return 0;
            }
            
            if (String.IsNullOrEmpty(s1)) {
                return s2.Length * INSERTION_COST;
            }
            
            if (String.IsNullOrEmpty(s2)) {
                return s1.Length * DELETION_COST;
            }
            
            int[,] matrix = new int[s1.Length + 1, s2.Length + 1];
            
            for (int i = 0; i < matrix.GetLength(0); i++) {
                for (int j = 0; j < matrix.GetLength(1); j++) {
                    if (i == 0) {
                        matrix[i,  j] = j * INSERTION_COST;
                    }
                    else if (j == 0) {
                        matrix[i, j] = i * DELETION_COST;
                    } else if (s1[i - 1] == s2[j - 1]) {
                        matrix[i, j] = matrix[i - 1, j - 1];
                    } else {
                        int candidate1 = SUBSTITUTION_COST + matrix[i - 1, j - 1];
                        int candidate2 = INSERTION_COST + matrix[i, j - 1];
                        int candidate3 = DELETION_COST + matrix[i - 1, j];
                        int minCost = Math.Min(candidate1, candidate2);
                        matrix[i, j] = Math.Min(minCost, candidate3);
                    }
                }
            }
            
            return matrix[s1.Length, s2.Length];
        }
    }
}