Skip to Content

Edit Distance

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 4 months ago

Related Problems

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Given an integer array nums, find a subarray that has the largest product, and return the product.