Eric Yuan's Blog

Perstando et Praestando

  • About Me

[LeetCode] Edit Distance

January 16, 2014 / Leave a Comment

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Find minimum number of steps, then it must be a Dynamic Programming problem. Only thing we need is a recursive definition of this problem.

We can define data(i, j) as the Edit Distance of the first i characters of word1 and first j characters of word 2, so when word1[i] is equal to word2[j], data(i, j) will be the same as data(i – 1, j – 1), because we need nothing to change word1[i] to word2[j]; when word1[i] is not equal to word2[j], then data(i, j) will be the minimum of (data(i, j – 1), data(i – 1, j), data(i – 1, j – 1)) plus 1. Of course, when i is equal to 0, data(0, j)’s value is j, because i = 0, means this substring has 0 character, so it will take j steps to change this empty substring to the j-length substring, and the same reason to data(i, 0).

    int minDistance(string word1, string word2) {
        if(word1.empty() && word2.empty()) return 0;
        if(word1.empty()) return word2.length();
        if(word2.empty()) return word1.length();
        if(word1 == word2) return 0;
        int len1 = word1.length() + 1;
        int len2 = word2.length() + 1;
        if(len1 == 2 && len2 == 2) return 1;
        int **data = new int*[len1];
        for(int i=0; i<len1; i++){
            data[i] = new int[len2];
        }
        for(int i=0; i<len1; i++){
            data[i][0] =  i;
        }
        for(int i=0; i<len2; i++){
            data[0][i] =  i;
        }
        for(int i=1; i<len1; i++){
            for(int j=1; j<len2; j++){
                if(word1[i-1] == word2[j-1]){
                    data[i][j] = data[i-1][j-1];
                }else{
                    data[i][j] = min(min(data[i-1][j], data[i][j-1]), data[i-1][j-1]) + 1;
                }
            }
        }
        int result = data[len1 - 1][len2 - 1];
        return result;
    }

 

🙂

Posted in: Algorithm, Dynamic Programming, LeetCode Tagged: Algorithm, Dynamic Programming, LeetCode

Pages

  • About Me

Categories

  • Algorithm
  • Deep Learning
  • Dynamic Programming
  • Graphics
  • LeetCode
  • Machine Learning
  • Machine Reading Comprehension
  • Maths
  • NLP
  • OpenCV
  • Something else
  • Twaddle
  • Uncategorized
  • Vision

Archives

  • July 2016
  • August 2015
  • June 2015
  • April 2015
  • March 2015
  • October 2014
  • September 2014
  • July 2014
  • June 2014
  • May 2014
  • April 2014
  • March 2014
  • February 2014
  • January 2014
  • November 2013
  • October 2013
  • September 2013

Copyright © 2018 Eric Yuan's Blog.

Me WordPress Theme by themehall.com