Edit Distance

Home | Coding Interviews | Dynamic Programming | Edit Distance

Dynamic Programming Hard Video Code Solution Java

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character

Delete a character

Replace a character

Edit distance is a canonical dynamic programming problem which is probably why leetcode marks it as medium difficulty. But it's logically hard in my opinion. The difficulty ratings have an issue in that some things you are expected to have seen before simply because they are so well known, and once you have seen the solution once it becomes somewhat easy to reproduce.

class Solution {
  public int minDistance(String word1, String word2) {
    final int m = word1.length();//first word length
    final int n = word2.length();///second word length
    // dp[i][j] := min # of operations to convert word1[0..i) to word2[0..j)
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; ++i)
      dp[i][0] = i;

    for (int j = 1; j <= n; ++j)
      dp[0][j] = j;

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (word1.charAt(i - 1) == word2.charAt(j - 1))//same characters
          dp[i][j] = dp[i - 1][j - 1];//no operation
        else
          dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;//replace,delete,insert

    return dp[m][n];
  }
}

Posted by Jamie Meyer 8 months ago

Edit Distance

Related Problems