Question

Formatted question description: https://leetcode.ca/all/72.html

72	Edit Distance

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

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
    horse -> rorse (replace 'h' with 'r')
    rorse -> rose (remove 'r')
    rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
    intention -> inention (remove 't')
    inention -> enention (replace 'i' with 'e')
    enention -> exention (replace 'n' with 'x')
    exention -> exection (replace 'n' with 'c')
    exection -> execution (insert 'u')

Algorithm

DFS

For the two characters word1[i] and word2[j] currently compared, if they are the same, skip to the next position directly.

If they are not the same, there are three treatment methods,

First, insert a word2[j] directly, then the character at word2[j] will be skipped, and then compare word1[i] and word2[j+1].
The second method is to delete, that is, delete the characters in word1[i] directly, and then compare word1[i+1] and word2[j].
The third is to modify word1[i] to word2[j], and then compare word1[i+1] and word[j+1].

At this point in the analysis, you can write the recursive code directly, but unfortunately it will be Time Limited Exceed, so the time complexity must be optimized, and a large amount of repeated calculations need to be removed.

Here, the memory array memo is used to save the calculated state, so that you can Through OJ, note that the insertCnt, deleteCnt, and replaceCnt here just indicate that the current corresponding position uses insert, delete, and replace operations, respectively. The overall return minimum distance, the latter position will still call recursion to return the smallest

DP

Here we need to maintain a two-dimensional array dp, whose size is m*n, and m and n are the lengths of word1 and word2 respectively.

dp[i][j] represents the steps required to convert from the first i characters of word1 to the first j characters of word2. First assign a value to the first row and first column of the two-dimensional array dp.

This is very simple, because there is always a string corresponding to the first row and the first column that is an empty string, so the conversion step is completely the length of another string . Similar to the previous DP problem, the difficulty lies in finding the state transition equation. Take an example. For example, word1 is “bbc” and word2 is “abcd”. You can get the dp array as follows:

  Ø a b c d
Ø 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2

When word1[i] == word2[j], dp[i][j] = dp[i-1][j-1], in other cases, dp[i][j] is its left and upper left, The minimum value of the three values above is increased by 1. In fact, the left, top, and top left here correspond to the addition, deletion, and modification operations respectively. For details, please refer to the explanation part of the first solution, then the state transition equation can be obtained as

dp[i][j] =      /    dp[i - 1][j - 1]                                                                   if word1[i - 1] == word2[j - 1]

                  \    min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1            else

Code

public class Edit_Distance {

	public class Solution {
	    public int minDistance(String w1, String w2) {

	        if (w1 == null || w2 == null) {
	            return 0;
	        }

	        // dp[i][j]
	        int[][] dp = new int[w1.length() + 1][w2.length() + 1];

	        // initiation
	        // dp[0][0] = 0;
	        for (int i = 1; i < w2.length() + 1; i++) {
	            // case when w1 is empty string
	            dp[0][i] = i;
	        }
	        for (int i = 1; i < w1.length() + 1; i++) {
	            // case when w2 is empty string
	            dp[i][0] = i;
	        }

	        for (int i = 1; i < w1.length() + 1; i++) {
	            for (int j = 1; j < w2.length() + 1; j++) {

	                if (w1.charAt(i - 1) == w2.charAt(j - 1)) {
	                    dp[i][j] = dp[i - 1][j - 1];
	                } else {
	                    int tmpMin = Math.min(dp[i - 1][j], dp[i][j - 1]);
	                    tmpMin = Math.min(tmpMin, dp[i - 1][j - 1]);
	                    dp[i][j] = 1 + tmpMin;
	                }
	            }
	        }

	        return dp[w1.length()][w2.length()];
	    }
	}


	// recursion method, "Time Limit Exceeded"
	public class Solution_recursion {

	    public int minDistance(String w1, String w2) {

	        if (w1.length() == 0 || w1 == null)   return w2.length();
	        if (w2.length() == 0 || w2 == null)   return w1.length();

	        if (w1.length() > w2.length())      return minDistance(w2, w1);

	        if (w1.charAt(0) == w2.charAt(0)) {

	            return minDistance(w1.substring(1), w2.substring(1)); // @note: this is the min possible, no need to try the other 2 possibility (i+1,j) or (i,j+1)
	        }

	        else {
	            int delete = minDistance(w1, w2.substring(1)) + 1;
	            int replace = minDistance(w1.substring(1), w2.substring(1)) + 1;

	            return Math.min(delete, replace);
	        }
	    }
	}

	class Solution_recursion2 {
		int min = Integer.MAX_VALUE;

		public int minDistance(String word1, String word2) {
			if (word1 == null || word2 == null) {
				return -1;
			}

			if (word1.length() > word2.length()) {
				return minDistance(word2, word1);
			}

			dfs(word1, word2, 0, 0, 0);
			return min;
		}

		private void dfs(String word1, String word2, int i, int j, int count) {

//            System.out.println("i:"+i+", j:"+j);

			// word1 is the shorter string
			if (i == word1.length()) { // reaching end

				int distance = count + word2.length() - j;
				min = Math.min(min, distance);
				return;
			}

			if (j == word2.length()) { // @note: case: 'aaaaaaa', 'ab', now i is larger than j
				int distance = count + word1.length() - i;
				min = Math.min(min, distance);
				return;
			}

			if (i > word1.length() || j > word2.length()) {
				return;
			}

			int extra = word1.charAt(i) == word2.charAt(j) ? 0: 1;

			dfs(word1, word2, i + 1, j, count + 1);
			dfs(word1, word2, i, j + 1, count + 1);
			dfs(word1, word2, i + 1, j + 1, count + extra);
		}
	}

}

############

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; ++i) {
            dp[i][0] = i;
        }
        for (int j = 0; 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)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

// OJ: https://leetcode.com/problems/edit-distance
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int minDistance(string A, string B) {
        if (A.empty() || B.empty()) return max(A.size(), B.size());
        int M = A.size(), N = B.size();
        vector<vector<int>> dp(M + 1, vector<int>(N + 1));
        for (int i = 0; i < M; ++i) dp[i + 1][0] = i + 1;
        for (int j = 0; j < N; ++j) dp[0][j + 1] = j + 1;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i] == B[j]) dp[i + 1][j + 1] = dp[i][j];
                else dp[i + 1][j + 1] = 1 + min({ dp[i][j], dp[i][j + 1], dp[i + 1][j] });
            }
        }
        return dp[M][N];
    }
};

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else: # dp[i - 1][j - 1]) meaning replace. e.g. "abc" and "bf", checking "ab" and "b" distance, then replace either way for "c" or "f"
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
        return dp[-1][-1]

############

class Solution(object):
  def minDistance(self, word1, word2):
    """
    :type word1: str
    :type word2: str
    :rtype: int
    """
    if len(word1) == 0 or len(word2) == 0:
      return max(len(word1), len(word2))

    dp = [[0] * (len(word2) + 1) for _ in range(0, len(word1) + 1)]
    dp[0][0] = 0

    for i in range(0, len(word1) + 1):
      for j in range(0, len(word2) + 1):
        if i == 0:
          dp[i][j] = j
        elif j == 0:
          dp[i][j] = i
        else:
          cond1 = dp[i][j - 1] + 1
          cond2 = dp[i - 1][j] + 1
          cond3 = 0
          if word1[i - 1] == word2[j - 1]:
            cond3 = dp[i - 1][j - 1]
          else:
            cond3 = dp[i - 1][j - 1] + 1
          dp[i][j] = min(cond1, cond2, cond3)
    return dp[-1][-1]

func minDistance(word1 string, word2 string) int {
	m, n := len(word1), len(word2)
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
			}
		}
	}
	return dp[m][n]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

72 - Edit Distance

Question

Algorithm

DFS

DP

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

DFS

DP

Code

All Problems

All Solutions