Introduction
It is such great mocking experience for Julia to work on edit distance algorithm again in 30 minutes this afternoon around 4:00 pm. Since Julia was tired and kind of sleepy, she could not hear the peer because of her speaker was turned off. It took her 5 minutes to find out, both tried to login again. The fact is that if you are tired, your will have some issues to work on the small thing.
It is good to observe that when you are tired, the thing can go out of control once a while. Julia remembered last time that she was very tired and then she worked on week of code 34 over 5 hours and did not score anything. Always get ready for the mocking!
The algorithm is hard to write. Even though it is not the first time to write it. Her last practice is documented here.
Design of Memoization
The peer helped Julia to come out the idea to design the key for memoization. Julia worked on design by going through the simple case, "heat" to "hit", how to express distance("eat","it") using the key? Julia thought about loud, one way is to concatenate two keys like this "eat it", and she said that "it eat" should be the same as "eat it". Because Julia was too tired, she did not have a good idea. She was given a hint to use the array, use index of string, then she asked the idea using int[2] and define the comparer function.
The peer gave her hint to use jagged array memo[i][j], whereas i and j are the index of start position of substring.
Algorithm practice
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
class Solution | |
{ | |
public static int DeletionDistance(string str1, string str2, int index1, int index2, int[][] memo) | |
{ | |
// your code goes here | |
if((str1 == null || str1.Length == 0 ) && | |
(str2 == null || str2.Length == 0)) | |
{ | |
return 0; | |
} | |
if(str1 == null || str1.Length == 0) | |
{ | |
return str2.Length; | |
} | |
if(str2 == null || str2.Length == 0) | |
{ | |
return str1.Length; | |
} | |
if(index1 == str1.Length) | |
{ | |
return str2.Length - index2; | |
} | |
if(index2 == str2.Length) | |
{ | |
return str1.Length - index1; | |
} | |
int length1 = str1.Length; | |
int length2 = str2.Length; | |
if(memo == null) // memo "dog", "frog" | |
{ | |
memo = new int[length1][]; | |
for(int i = 0; i < length1; i++) | |
{ | |
memo[i] = new int[length2]; | |
} | |
for(int row = 0; row < length1; row ++) | |
{ | |
for(int col = 0; col < length2; col ++) | |
{ | |
memo[row][col] = -1; | |
} | |
} | |
} | |
bool noMemo = memo[index1][index2] == -1; | |
if(!noMemo) | |
{ | |
return memo[index1][index2]; | |
} | |
// recursive call | |
var isEqual = str1[index1] == str2[index2]; | |
int distance = 0; | |
if(isEqual) | |
{ | |
distance = DeletionDistance(str1, str2, index1 + 1, index2 + 1, memo); // delete, 0 | |
} | |
else | |
{ | |
var option1 = 1 + DeletionDistance(str1, str2, index1 + 1, index2, memo); // delete one char | |
var option2 = 1 + DeletionDistance(str1, str2, index1 , index2 + 1, memo); // delete one char | |
distance = Math.Min(option1, option2); | |
} | |
memo[index1][index2] = distance; | |
return distance; | |
} | |
static void Main(string[] args) | |
{ | |
} | |
} | |
//dog -> frog | |
// heat -> hit , h -> eat vs it , e != i, | |
// remove e, dist("at","it") | |
// remove i, dist("eat","t") | |
// Math.Min(dist("at","it"), dist("eat","t")), memoization key string "at it", "it at" | |
// left -> right, index , index -> unique -> int[] key int[2], compare function | |
//memo[i][j] jagged array i, j already store | |
// base case: | |
// "", "abc" |
Editorial Notes:
9/22/2017I practiced again this algorithm through mocking interview, I met a senior developer who has very good managing experience. He asked me the time complexity about brute force solution, I stumbled on the question.
Based on the above experience, I did not learn the algorithm very well in theory. The dynamic programming is not easy to figure out. I need to relate to a simple life experience for this algorithm. I did one later on. Here is the blog link.
July 6 2023
I am working on Meta phone screen in two months, so I have chance to review Edit distance.
No comments:
Post a Comment