Edit Distance

Problem Statement

A classic in Dynamic Programming-based problems, Edit Distance is the entry point into string dp. The problem is straightforward: given two input strings, return the minimum number of operations it takes to turn one string into the other. Here, an operation is either: delete a character, replace a character, or add a character.

Brute Force

Clearly, the brute force approach here would be to simulate every operation and find the answer. This wouldn't even be simple, as you would need to set rules up for when you can add/delete characters or else it would just go on foreverIn the case of just infinitely adding characters. There isn't too much to say here, except for the fact that it is clearly not a solution that would pass an interview or even leetcode timing rules.

Dynamic Programming

We must, then, come up with a faster way of computing this. In general, on problems that have massive brute force runtimes from overlapping computation/states, dynamic programming is the way to go. Step one of creating a DP program is identifying the state we track at each point. Intuitively, we want to track the number of operations it takes to make the subproblem complete. Step two, or honestly this should be step one, is to identify the subproblems. What can we iteratively build on top of to come up with a solution? If you thought of substrings, then you are correct. We now know that this will be a 2D DP problem, with one dimension representing the characters of one word and the other dimension representing the characters of the other word. At each index dp[i][j], there are three options:

1. Delete a character
2. Replace a character
3. Insert a character

If you drew out a grid, each of these represents a different previous location that we can build on top of. dp[i][j-1] gets the number of operations it took to make the current word1 substring equal to one character shorter of the word2 substring. So dp[i][j-1] + 1 is the delete option. Conversely, dp[i-1][j] is the insert option. Finally, dp[i-1][j-1] signals a replace because you just replace one character either in word1 or word2 to match the other word without a delete or anything. The implementation is simple once you understand this. All that needs to be done is to set up the grid, build the base case which are the first row and the first column, and then apply this logic. A subtlety I forgot to mention but should be clear is that if you ever encounter an index where word1[i] == word2[j], then you don't need to increment anything as no operation is required. Here is my solution:

def minDistance(self, word1: str, word2: str) -> int:
	word1_len = len(word1)
	word2_len = len(word2)
	if word1_len == 0:
		return word2_len
	if word2_len == 0:
		return word1_len
	dp = [[-1] * word2_len for _ in range(word1_len)]
	
	# Fill in first row
	dp[0][0] = 0 if word2[0] == word1[0] else 1
	skipped = dp[0][0] == 0
	for i in range(1,word2_len):
		if word2[i] == word1[0] and not skipped:
			dp[0][i] = dp[0][i-1]
			skipped = True
		else:
			dp[0][i] = dp[0][i-1] + 1
			
	# Fill in first column
	skipped = dp[0][0] == 0
	for j in range(1,word1_len):
		if word2[0] == word1[j] and not skipped:
			dp[j][0] = dp[j-1][0]
			skipped = True
		else:
			dp[j][0] = dp[j-1][0] + 1
			
	for i in range(1,word2_len):
		for j in range(1,word1_len):
			# Insert, Replace, or Delete
			if word2[i] == word1[j]:
				dp[j][i] = dp[j-1][i-1]
			else:
				dp[j][i] = min(dp[j][i-1] + 1, dp[j-1][i] + 1, dp[j-1][i-1] + 1)
	
	# The answer always propogates to the end of both words
	return dp[-1][-1]