Given two strings
word2, return the minimum number of steps required to make
word2 the same.
In one step, you can delete exactly one character in either string.
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".
Input: word1 = "leetcode", word2 = "etco" Output: 4
1 <= word1.length, word2.length <= 500
word2consist of only lowercase English letters.
The problem might sound familiar to classic dynamic programming questions however we should focus that we can only delete the words. If we were allowed to update / insert / delete the characters then it would have become the Edit Distance Problem using Dynamic Programming. Because we are only allowed using the delete operation, the problem translates to finding the number of characters that are different in both the strings (or finding the common ones?). If We can easily find the common subsequence characters and subtract double the common length from the combined length, it would give us the letters we want to delete. We can use the Longest Common Subsequence for that and we will briefly discuss about the algorithm and I would put more references in case you want to learn more about the algorithm.
Longest Common subsequence
To determine the length of the LCS between all combinations of substrings of
b, we can use a dynamic programming technique. Dynamic programming basically means that you compute all possibilities and store them inside a look-up table.
To find the lengths of all possible subsequences, we use a helper function,
lcsLength(_:). This creates a matrix of size
matrix[x][y] is the length of the LCS between the substrings
Lets take an example for
"ABDCAB". The following would look something like this:
| | Ø | A | B | D | C | A | B | | Ø | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | A | 0 | 1 | 1 | 1 | 1 | 1 | 1 | | B | 0 | 1 | 2 | 2 | 2 | 2 | 2 | | C | 0 | 1 | 2 | 2 | 3 | 3 | 3 | | B | 0 | 1 | 2 | 2 | 3 | 3 | 4 | | X | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
Note that the elements first row and the first column are 0 since we are comparing with the empty string. In this example, if we look at
matrix we find the value
3. This means the length of the LCS between
b[0...3], or between
"ABDC", is 3.
The time and space complexity would remain same as the LCS operation. We are using two nested loops to compute the DP array hence m * n operations where m, n are the length of the input strings. Space complexity would also be same for saving 2D matrix.
Time = O(M * N)
Space = O(M * N)