Leetcode 72: Edit Distance

Sept. 11, 2017

Introduction

It is one of classical algorithms related to recursive function and also memoization. I have practiced a few times and I am still learning the algorithm. My last practice is documented here, and all past practices are available through the search by Leetcode 72.

It was such great experience to be interviewed using the algorithm again. This is my third algorithm practice, my last practice was more than one month ago. I still remembered the mistake I had and the advice I got from the peer.

Algorithm practice 

Here is my C# code written in 30 minutes. I had a mocking experience starting from 10:00 pm.

	using System;
	class Solution
	{
	public static int DeletionDistance(string str1, string str2)
	{
	// your code goes here
	if((str1 == null || str1.Length == 0 ) && ( str2 == null || str2.Length == 0))
	{
	return 0;
	}
	// assume that one of is not empty
	if(str1 == null || str1.Length == 0)
	{
	return str2.Length;
	}
	if(str2 == null || str2.Length == 0)
	{
	return str1.Length;
	}
	var length1 = str1.Length;
	var length2 = str2.Length;
	var memo = new int[length1][];
	for(int row = 0; row < length1; row++)
	{
	memo[row] = new int[length2];
	for(int col = 0; col < length2; col++)
	{
	memo[row][col] = -1; // not set
	}
	}
	return DeletionDistanceHelper(str1, str2, 0, 0, memo);
	}
	private static int DeletionDistanceHelper(string str1, string str2, int index1, int index2, int[][] memo)
	{
	var length1 = str1.Length;
	var length2 = str2.Length;
	if(index1 == length1)
	{
	return length2 - index2; // outside ->
	}
	if(index2 == length2)
	{
	return length1 - index1;
	}
	var hasMemo = memo[index1][index2] != -1 ;
	if(hasMemo)
	{
	return memo[index1][index2];
	}
	var visit1 = str1[index1];
	var visit2 = str2[index2];
	var isEqual = visit1 == visit2;
	// check if need to update memo
	var distance = 0;
	if(isEqual)
	{
	distance = DeletionDistanceHelper(str1, str2, index1 + 1, index2 + 1, memo);
	}
	else
	{
	// delete one of chars in two strings
	distance = 1 + Math.Min(DeletionDistanceHelper(str1, str2, index1 + 1, index2, memo),
	DeletionDistanceHelper(str1, str2, index1, index2 + 1, memo));
	}
	memo[index1][index2] = distance; // do not calculate twice
	return distance;
	}
	static void Main(string[] args)
	{
	}
	}
	// dynamic program -> recursive -> memo
	// heat -> hit distance 3
	// 'h' == 'h',
	// index1 for heat -> distance same, index1 ++
	// index2 for hit index2 ++
	// 'e' ?= 'i', delete 'e' or delete 'i'
	// Min(dist("at", "it"), dist("eat", "t")) + 1, count deletion, increment one
	// memo use jagged array to express memo
	// "heat" - 4
	// "hit" - 3
	// memo[4][3],
	// memo[row][0] = row, for any row from 0 to 3
	// memo[0][col] = col, for any column for o to 2
	// recursive, memoization
	// n * m , n is length of str1, m is length of str2 - wrong
	// 2^max(n, m) - without memoization ->
	// with memoization, n * m

view raw Leetcode72 EditDistance Practice Deletion Distance.cs hosted with ❤ by GitHub

I knew that I have to work hard to be an interviewer in order to get unlimited credit. I just started my new round of mocking practice. I could not memorize the algorithms, there are a lot of new issues coming out on this algorithm. I failed to do analysis of brute force solution, it should be 2^{(max(str1.Length, str2.Length))}, because every time there is at most 2 choices. I was given the hint and then I took the hint to go from n * m to power of 2 analysis. In other words, the time complexity is lowered from polynomial time to quadratic time.

Assume that the worst case happens. In other words, the comparison of two chars are not equal, so one of them has to be deleted. There are two choices to do deletion, the minimum value of two choices will be recorded. For example, two strings are "abc" and "edfg". The total choices are at most 2⁷. In mathematical term, the upper bound is 2⁷ = 512. The dynamic programming using memoization will lower time complexity using jagged array memo[3][4], time complexity 3 * 4 = 12.

I also was told to make correction on the first line of the function, line 8. The checking is for the case of both strings are null or empty. Not at least one of them. I wrote || by the mistake.

Related to a simple life choice

9/12/2016

It is always good idea to write down the practice experience, what did I actually learn from the mocking? This time, 30 minutes coding passes all test cases, with one of corrections from the peer. But I was surprised to know that I need to grasp the basic algorithm analysis, as I shared my knowledge of Monte Carlo algorithm to a young graduate from a linguistic major, I have to explain the algorithm to myself. The most important is to know how to analyze instead of guessing.


If I have two choices to calculate distance, how should I make a decision? I have to go for the minimum one from the two choices. If I have a series of choices to make, then the combinations of choices will be 2ⁿ. To summarize, Leetcode 72 is the algorithm for me to teach myself how to understand the brute force solution with polynomial time complexity, know how to solve the problem first, and then apply dynamic programming, lower the time complexity to m * n using memoization, dynamic programming using bottom up solution.

It is interesting to know the memoization design, the best choice I know is to use jagged array, memo[][], the size of jagged array is str1.Length * str2.Length, that is how many intermediate result we have to hold. Assume that each of them is calculated to use a few simple steps which are O(1) time complexity.