LC072 - Edit Distance

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

Example

Input: word1 = "horse", word2 = "ros"

Output: 3

Explanation:

• horse -> rorse (replace 'h' with 'r')

• rorse -> rose (remove 'r')

• rose -> ros (remove 'e')

Solution

2D Dynamic Programming

This question came up before in my Speech and Language Processing course, and the taught method was a 2D DP approach, so we will go straight to it.

def minDistance(self, word1: str, word2: str) -> int:
	arr = [[float("inf") for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]

	for j in range(len(word2) + 1):
		arr[len(word1)][j] = len(word2) - j
	for i in range(len(word1) + 1):
		arr[i][len(word2)] = len(word1) - i 

	# for length of words:
	for i in range(len(word1)-1, -1, -1):
		for j in range(len(word2)-1, -1, -1):
			if word1[i] == word2[j]:
				arr[i][j] = arr[i+1][j+1]
			else:
				arr[i][j] = 1 + min(arr[i+1][j], arr[i][j+1], arr[i+1][j+1])
				
	return arr[0][0]