583. Delete Operation for Two Strings

LeetCode 583. Delete Operation for Two Strings

Description

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.

Tags

Dynamic Programming, String

Solution

双串LCS问题。按本题操作后得到的结果就是最长公共子序列，因此删除掉的字符数目就是两字符串长度和减去2倍LCS。

Follow the instruction and the processed 2 strings we obtained are ought to the same as that in LeetCode 1143. Longest Common Subsequence. Thus, the result is equal to len(word1) + len(word2) - 2*lcs.

Complexity

• Time complexity: $O(n^2)$

• Space complexity: $O(n^2)$

Code

func minDistance(word1 string, word2 string) int {
	lcs := longestCommonSubsequence(word1, word2)
	return len(word1) + len(word2) - 2*lcs
}

func longestCommonSubsequence(text1 string, text2 string) int {
	dp := make([][]int, len(text1)+1)
	for i := range dp {
		dp[i] = make([]int, len(text2)+1)
	}
	for i := 1; i <= len(text1); i++ {
		for j := 1; j <= len(text2); j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = 1 + dp[i-1][j-1]
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			}
		}
	}
	return dp[len(text1)][len(text2)]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}