Problem

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 or substitute a character

Examples

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')

Solution

Method 1 - Recursion

  • Got TLE since we recursively solve the same subproblem several times.

Code

Java
/**
     * For each poisition, check three subproblem:
     * 1. insert
     * 2. delete
     * 3. replace
     * We only modify the first string since no matter which one we choose, the result is the same. 
     * Need to optimize it using cache, which is the idea of dynamic programming. 
     * The key point is to find out the subproblem we have solved duplicately and cache the recursion.
     * Noticed that each subproblem is specificed by i and j pointer, so we can cache the result of these subproblems. 
     */
public int minDistance(String word1, String word2) {
	if (word1 == null || word1.length() == 0) return word2.length();
	if (word2 == null || word2.length() == 0) return word1.length();
	
	return match(word1, word2, 0, 0);
}

private int match(String s1, String s2, int i, int j) {
	//If one of the string's pointer have reached the end of it
	if (s1.length() == i) {
		return s2.length() - j;
	}
	if (s2.length() == j) {
		return s1.length() - i;
	}
	
	int res;
	//If current poisition is the same.
	if (s1.charAt(i) == s2.charAt(j)) {
		res = match(s1, s2, i + 1, j + 1);
	} else {
		//Case1: insert
		int insert = match(s1, s2, i, j + 1);
		//Case2: delete
		int delete = match(s1, s2, i + 1, j);
		//Case3: replace
		int replace = match(s1, s2, i + 1, j + 1);
		res = Math.min(Math.min(insert, delete), replace) + 1;
	}
	
	return res;
}

Complexity

  • ⏰ Time complexity: O(3^max(m, n)) where m and n is length of word word1 and word2. We do 3^x, because we have 3 options to choose from, insert, delete or substitute.
  • 🧺 Space complexity: O(max(m, n))

Method 2 - Top Down DP with Memoization

Code

Java
public int minDistance(String word1, String word2) {
	if (word1 == null || word2 == null) return -1;
	if (word1.length() == 0) return word2.length();
	if (word2.length() == 0) return word1.length();
	
	char[] c1 = word1.toCharArray();
	char[] c2 = word2.toCharArray();
	
	int[][] cache = new int[c1.length][c2.length];
	for (int i = 0; i < c1.length; i++) {
		for (int j = 0; j < c2.length; j++) {
			cache[i][j] = -1;
		}
	}
	
	return match(c1, c2, 0, 0, cache);
}

private int match(char[] c1, char[] c2, int i, int j, int[][] cache) {
	if (c1.length == i) return c2.length - j;
	if (c2.length == j) return c1.length - i;
	
	if (cache[i][j] != -1) {
		return cache[i][j];
	}
	
	if (c1[i] == c2[j]) {
		cache[i][j] = match(c1, c2, i + 1, j + 1, cache);
	} else {
		//Case1: insert
		int insert = match(c1, c2, i, j + 1, cache);
		//Case2: delete
		int delete = match(c1, c2, i + 1, j, cache);
		//Case3: replace
		int replace = match(c1, c2, i + 1, j + 1, cache);
		
		cache[i][j] = Math.min(Math.min(insert, delete), replace) + 1;
	}
	
	return cache[i][j];
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n)

Method 3 - Bottom up DP

Code

Java
public int minDistance(String word1, String word2) {
	if (word1 == null || word2 == null) return -1;
	if (word1.length() == 0) return word2.length();
	if (word2.length() == 0) return word1.length();
	
	char[] c1 = word1.toCharArray();
	char[] c2 = word2.toCharArray();
	
	int[][] matched = new int[c1.length + 1][c2.length + 1];
	//matched[length of c1 already been matched][length of c2 already been matched]
	
	for (int i = 0; i <= c1.length; i++) {
		matched[i][0] = i;
	}
	for (int j = 0; j <= c2.length; j++) {
		matched[0][j] = j;
	}
	
	for (int i = 0; i < c1.length; i++) {
		for (int j = 0; j < c2.length; j++) {
			if (c1[i] == c2[j]) {
				matched[i + 1][j + 1] = matched[i][j];
			} else {
				matched[i + 1][j + 1] = Math.min(Math.min(matched[i][j + 1], matched[i + 1][j]), matched[i][j]) + 1;
				//Since it is bottom up, we are considering in the ascending order of indexes.
				//Insert means plus 1 to j, delete means plus 1 to i, replace means plus 1 to both i and j. 
				//above sequence is delete, insert and replace. 
			}
		}
	}
	
	return matched[c1.length][c2.length];
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(m*n)