Leetcode 72: Edit Distance

June 21, 2017

Introduction

Plan to work on Leetcode 72: Edit Distance again. The problem statement is here.

Algorithm study 

Julia's C# practice is here. 

Follow up

Dec. 10, 2019 10:49 PM

	using System;
	using System.Collections.Generic;
	using System.Diagnostics;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace EditDistance
	{
	class Program
	{
	static void Main(string[] args)
	{
	RunTestcase();
	RunTestcase2();
	RunTestcase3();
	}
	public static void RunTestcase()
	{
	int result1 = minDistance("abc", "abcd");
	Debug.Assert(result1 == 1);
	}
	public static void RunTestcase2()
	{
	int result1 = minDistance("abc", "bca");
	Debug.Assert(result1 == 2);
	}
	public static void RunTestcase3()
	{
	int result1 = minDistance("abc", "cba");
	Debug.Assert(result1 == 2);
	}
	/// <summary>
	/// June 22, 2017
	/// Code review again after 24 months
	///
	/// June 17, 2015
	/// source code reference:
	/// http://blog.csdn.net/fightforyourdream/article/details/13169573
	/// there is a table to explain how to build this distance table:
	///
	/// </summary>
	/// <param name="word1"></param>
	/// <param name="word2"></param>
	/// <returns></returns>
	public static int minDistance(String word1, String word2)
	{
	int length1 = word1.Length;
	int length2 = word2.Length;
	// consider to add empty space string
	var distance = new int[length1 + 1][];
	for (int i = 0; i < length1 + 1; i++)
	{
	distance[i] = new int[length2 + 1];
	}
	// base case: one thing is empty, then distance is another string's length
	for (int i = 0; i < length1 + 1; i++)
	{
	distance[i][0] = i;
	}
	for (int j = 1; j < length2 + 1; j++)
	{
	distance[0][j] = j;
	}
	// recursive，[i][j] depends on left，top and left top 3 situations
	for (int i = 1; i < length1 + 1; i++)
	{
	var current1 = word1[i - 1];
	for (int j = 1; j < length2 + 1; j++)
	{
	var current2 = word2[j - 1];
	// If last characters of two words are the same, then it is 0.
	// If they are different, then it is 1.
	var distanceValue = (current1 == current2) ? 0 : 1;
	var top = distance[i - 1][j];
	var left = distance[i][j - 1];
	var leftTop = distance[i - 1][j - 1];
	// from top or from left, both needs insertion
	var minimum = Math.Min(top + 1, left + 1);
	// from top left, consider substitution
	distance[i][j] = Math.Min(minimum, leftTop + distanceValue);
	}
	}
	// return right bottom corner
	return distance[length1][length2];
	}
	}
	}

view raw Leetcode72_EditDistance_practice.cs hosted with ❤ by GitHub

It is better to add code to the blog. Also I spent 10 minutes to review the code, there are three cases involved to build next iteration in dynamic programming, left, top, and left and top, first two the increment is 1, last one may be one or zero, depending on last char in two strings are the same or not.

This definitely is a good practice question for dynamic programming.