Classic DP solution in C; 12 ms; 15 lines

  • 1
    int minof3(int x, int y, int z)
      x = (x<y)?x:y;
      return (x<z)?x:z;
    int minDistance(char* w1, char* w2) {
      //never trust the input
      if(w1 == NULL && w2==NULL) return 0;
      else if(w1 == NULL)        return strlen(w2);
      else if(w2 == NULL)        return strlen(w1);
      int l1 = strlen(w1);
      int l2 = strlen(w2);
      // dp[x][y] means the min edit distance from partial word1 (0..x-1) to partial word2 (0..y-1)
      // please note this takes O(mn) space; O(n) solution also available because only last iteration of result needs to be stored
      int dp[l1+1][l2+1];
      // init the dynamic programming matrix
      dp[0][0] = 0;
      for(int i = 1; i<=l1; i++) dp[i][0] = i;
      for(int j = 1; j<=l2; j++) dp[0][j] = j;
      for(int i = 1; i<=l1; i++)
        for(int j = 1; j<=l2; j++)
          if(w1[i-1] != w2[j-1])
            //different char; so adding/replacing/deleting all takes one more step
            dp[i][j] = minof3(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1;
            //same char; so no need to replace it; adding/deleting one still takes one more step
            dp[i][j] = minof3(dp[i][j-1]+1, dp[i-1][j-1], dp[i-1][j]+1);
      return dp[l1][l2];

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.