LeetCode Day 56 Dynamic Programming (16/17)

Dynamic planning is coming to an end, and I thought it was a lot of content for dynamic planning at the time, but it’s finish very quickly.

Question 1

583. Delete Operation for Two Strings

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.

This question compared to LC 115, in fact, is that both strings can be deleted, the situation is a little more complex, but the overall idea is the same

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]
        for i in range(len(word1)+1):
            dp[i][0] = i
        for j in range(len(word2)+1):
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1] + 2, dp[i-1][j] + 1, dp[i][j-1] + 1)
        return dp[-1][-1]

Question 2

72. Edit Distance

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

Edit Distance is a classic problem solved with a dynamic gauge, this problem may look like it’s complicated, but the minimum edit distance can be cleverly calculated using a dynamic gauge. Use the five parts of dynamic programming to do an analysis:

1. Determine the dp array (dp table) and what the subscripts mean

dp[i][j] denotes the string word1 ending with subscript i-1, and the string word2 ending with subscript j-1, with the nearest edit distance dp[i][j].

1. Determine the recursive formula

Overall, there are several operations as follows:

if (word1[i - 1] == word2[j - 1])
    No operation
if (word1[i - 1] != word2[j - 1])
    Insert
    Delete
    Replace

2.1 if (word1[i - 1] == word2[j - 1]) then it means that without any editing, dp[i][j] should be dp[i - 1][j - 1], i.e., dp[i][j] = dp[i - 1][j - 1]; 2.2 if (word1[i - 1] ! = word2[j - 1]), then you need to edit, how to edit it?

​ 2.2.1 Operation 1: word1 delete an element, then it is the following label i - 2 for the end of the word1 and j-1 for the end of the word2 of the nearest editing distance plus an operation. i.e. dp[i][j] = dp[i - 1][j] + 1; ​ 2.2.2 Operation 2: word2 delete an element, then is the subscript i - 1 for the end of the word1 and j-2 for the end of the word2 of the nearest edit distance plus an operation. That is dp[i][j] = dp[i][j - 1] + 1; ​ 2.2.3 Operation 3: Replace the element, word1 replace word1[i - 1] to make it the same as word2[j - 1], at this time do not have to add or delete elements.

1. how to initialise dp array

dp[i][j] denotes the string word1 ending with subscript i-1, and the string word2 ending with subscript j-1, with the nearest edit distance dp[i][j].

So what do dp[i][0] and dp[0][j] represent?

dp[i][0] : The string word1 ending with subscript i-1, and the empty string word2, with the nearest edit distance of dp[i][0].

Then dp[i][0] should be i, all the elements in word1 do delete operation, that is: dp[i][0] = i;

Similarly, dp[0][j] = j;

1. determine the traversal order

from the following four recursive formulas:

dp[i][j] = dp[i - 1][j - 1] dp[i][j] = dp[i - 1][j - 1] + 1 dp[i][j] = dp[i][j - 1] + 1 dp[i][j] = dp[i - 1][j] + 1 It can be seen that dp[i][j] is dependent on the left, top and upper left elements.

1. Derive the dp array by example

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]
        for i in range(len(word1)+1):
            dp[i][0] = i
        for j in range(len(word2)+1):
            dp[0][j] = j
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        return dp[-1][-1]