72. Edit Distance - 2015 practice

July 7, 2019

Introduction

It is my best favorite thing to do. What it is ?  Read my own code back in 2015. I was shy and also very close a person. Hard working, but I still like to explore more things. At that time, I remember that I ask my retired friend Rick if he likes to purchase a condo in the city of Seattle. I like to go out and drove my Ford Explorer SUV and cross border to shop clothes, hand bags. A lonely person likes to do things and enjoy road trip.  Certainly I do not know that there is a product feature called Discuss, I can share my practice over there, and also learn from other people as well.

My practice 

Today I like to review my practice. For me it is surprise and surprise. I need to review more often, since I learn the dynamic programming solution very well back in 2017 and 2018.

Here is my discussion post I write today.

It is so sweet to read my own code back in 2015. At that time, I started to work on leetcode algorithm, most of times I still google and found blogs written in Chinese, and then read the content I like most; at that time, I did not know there is a product feature called discuss on Leetcode.com. I did not know that there are over hundreds of sharing. I just could not believe that I was the person so close mind; not curious enough to press all possible links on Leetcode.com for a few hours, explore all possible resourceful places.

Lesson No. 1:
Good software programmer should be very curious person.

Another thing is that I should learn that Google search misses a lot of things, all Leetcode discuss will not find in any Google search as well.

All comments are in Chinese, but I will write down the tips for me to score all points in my writing next time.

Here are highlights:

1. Understand subproblems, there are only three subproblems, from three possible direction, up, left, and cross up left;
2. Greedy algorithm idea is to find the minimum value in all subproblems, go ahead to calculate three subproblems;
3. More about step 2, the difficult part is left top cross one. How to determine the minimum value based on the corner? Just replace one char with another one is second string if last char in both string are different;
4. Ask myself what is maxmimum difference between the current problem and subproblem, since add, delete and replace three choice, the difference is one.
5. If there is no choice to replace a char, then answer of step 4 question will be 2 for cross corner subprobelm case.

public class Solution {
    public int MinDistance(string word1, string word2) {
        int l1 = word1.Length; 
            int l2 = word2.Length; 

            int[][] distance = new int[l1+1][];
  
            for(int i = 0; i<l1+1;i++)
                distance[i] = new int[l2+1]; 
          
            // 边界情况：当其中一个string为空时，只要一直添加或删除就可以  
            for(int i=0; i< l1+1; i++){  
                distance[i][0] = i;  
            } 
 
            for(int j=1; j< l2+1; j++){  
                distance[0][j] = j;  
            }  
          
            // 递推，[i][j]处可以由左，上，左上3种情况而来  
            for(int i=1; i<l1+1; i++){  
                for(int j=1; j< l2+1; j++){  
                     int tmp = Math.Min(distance[i-1][j]+1,   // 从上演变  
                                        distance[i][j-1]+1); // 从左演变  
                 
                     // 从左上演变，考虑是否需要替换 
                     // avoid word1, word2 index out of range bug - how?
                     // word1: index range from 0->l1-1
                     // word2: index range from 0->l2-1
                     // but distance[i][j] is between word1's substring from 0 to i-1 and word2's substring from i to j-1
                     // there is one difference! 
                     distance[i][j] = Math.Min(tmp, distance[i-1][j-1]+((word1[i-1]==word2[j-1]) ? 0 : 1));                  
                }  
            }  

            // 返回右下角
            return distance[l1][l2];  
    }
}