72. Edit Distance

https://leetcode.com/problems/edit-distance/

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. 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')

---
Related problems
161-one-edit-distance
---
Intuition
Inserting character from 1 string is equivalent to deleting character from other string

	class Solution {
	public int minDistance(String s, String t) {
	Integer[][] memo = new Integer[s.length()][t.length()];
	return dfs(s, t, 0, 0, memo);
	}
	private int dfs(String s, String t, int i, int j, Integer[][] memo) {
	// termination - when one string exhausts, number of steps = remaining length of other string
	if (s.length() == i) {
	return t.length() - j;
	}
	if (t.length() == j) {
	return s.length() - i;
	}
	// check if combination of indices is already visited
	if (memo[i][j] != null) {
	return memo[i][j];
	}
	int ans = 0;
	if (s.charAt(i) == t.charAt(j)) {
	ans = dfs(s, t, i + 1, j + 1, memo);
	} else {
	// insert in shorter or delete in longer, or replace
	ans = 1 + Math.min(dfs(s, t, i + 1, j + 1, memo), Math.min(dfs(s, t, i, j + 1, memo), dfs(s, t, i + 1, j, memo)));
	}
	memo[i][j] = ans;
	return ans;
	}
	}

view raw 72.EditDistanceDFSMemoization.java hosted with ❤ by GitHub

	class Solution {
	public int minDistance(String word1, String word2) {
	if (word1 == null || word1.length() == 0) {
	return word2 != null ? word2.length() : 0;
	}
	if (word2 == null || word2.length() == 0) {
	return word1 != null ? word1.length(): 0;
	}
	int[][] cost = new int[2][word1.length() + 1];
	for (int c = 0; c < word1.length(); c++) {
	cost[0][c + 1] = c + 1;
	}
	for (int r = 1; r <= word2.length(); r++) {
	cost[1][0] = r;
	for (int c = 1; c <= word1.length(); c++) {
	if (word1.charAt(c - 1) == word2.charAt(r - 1)) {
	cost[1][c] = cost[0][c - 1];
	} else {
	cost[1][c] = 1 + Math.min(cost[0][c - 1], Math.min(cost[1][c - 1], cost[0][c]));
	}
	}
	System.arraycopy(cost[1], 0, cost[0], 0, word1.length() + 1);
	}
	return cost[1][word1.length()];
	}
	}

view raw 72.EditDistanceDPBottomUp.java hosted with ❤ by GitHub

	class Solution {
	public int minDistance(String word1, String word2) {
	int[][] cost = new int[word2.length() + 1][word1.length() + 1];
	for (int c = 0; c < word1.length(); c++) {
	cost[0][c + 1] = c + 1;
	}
	for (int r = 0; r < word2.length(); r++) {
	cost[r + 1][0] = r + 1;
	}
	for (int c = 1; c <= word1.length(); c++) {
	for (int r = 1; r <= word2.length(); r++) {
	if (word1.charAt(c - 1) == word2.charAt(r - 1)) {
	cost[r][c] = cost[r - 1][c - 1];
	} else {
	cost[r][c] = 1 + Math.min(cost[r - 1][c - 1], Math.min(cost[r][c - 1], cost[r - 1][c]));
	}
	}
	}
	return cost[word2.length()][word1.length()];
	}
	}

view raw 72.EditDistanceDFSMemoizationMoreSpace.java hosted with ❤ by GitHub

	class Solution:
	def minDistance(self, word1: str, word2: str) -> int:
	def dfs(i: int, j: int) -> int:
	if i == len(word1):
	return len(word2) - j
	if j == len(word2):
	return len(word1) - i
	if memo[i][j] is not None:
	return memo[i][j]
	ans = 0
	if word1[i] == word2[j]:
	ans = dfs(i + 1, j + 1)
	else:
	ans = 1 + min(dfs(i + 1, j + 1), min(dfs(i + 1, j), dfs(i , j + 1)))
	memo[i][j] = ans
	return ans
	memo = [[None] * len(word2) for _ in range(len(word1))]
	return dfs(0, 0)

view raw 72.EditDistance.py hosted with ❤ by GitHub