583. Delete Operation for Two Strings

Problem

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example 1:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Example 2:

Input: word1 = "leetcode", word2 = "etco"
Output: 4

Constraints:

• 1 <= word1.length, word2.length <= 500
• word1 and word2 consist of only lowercase English letters.

Problem Summary

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same. In each step, you can delete one character from either string.

Solution Approach

• Judging from the data size, this problem must be an O(n^2) dynamic programming problem. Define dp[i][j] as the minimum number of deletion steps needed to match word1[:i] and word2[:j]. If word1[:i-1] matches word2[:j-1], then dp[i][j] = dp[i-1][j-1]. If word1[:i-1] does not match word2[:j-1], then one deletion needs to be considered, so dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j]). Therefore, the state transition equation is:

  {{< katex display >}} dp[i][j] = \left{\begin{matrix}dp[i-1][j-1]&, word1[i-1] == word2[j-1]\ 1 + min(dp[i][j-1], dp[i-1][j])&, word1[i-1] \neq word2[j-1]\\end{matrix}\right. {{< /katex >}}

  The final answer is stored in dp[len(word1)][len(word2)].

Code

package leetcode

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}