Formatted question description: https://leetcode.ca/all/72.html
72 Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
For the two characters word1[i] and word2[j] currently compared, if they are the same, skip to the next position directly.
If they are not the same, there are three treatment methods,
- First, insert a word2[j] directly, then the character at word2[j] will be skipped, and then compare word1[i] and word2[j+1].
- The second method is to delete, that is, delete the characters in word1[i] directly, and then compare word1[i+1] and word2[j].
- The third is to modify word1[i] to word2[j], and then compare word1[i+1] and word[j+1].
At this point in the analysis, you can write the recursive code directly, but unfortunately it will be
Time Limited Exceed, so the time complexity must be optimized, and a large amount of repeated calculations need to be removed.
Here, the memory array memo is used to save the calculated state, so that you can Through OJ, note that the insertCnt, deleteCnt, and replaceCnt here just indicate that the current corresponding position uses insert, delete, and replace operations, respectively. The overall return minimum distance, the latter position will still call recursion to return the smallest
Here we need to maintain a two-dimensional array dp, whose size is m*n, and m and n are the lengths of word1 and word2 respectively.
dp[i][j] represents the steps required to convert from the first i characters of word1 to the first j characters of word2. First assign a value to the first row and first column of the two-dimensional array dp.
This is very simple, because there is always a string corresponding to the first row and the first column that is an empty string, so the conversion step is completely the length of another string . Similar to the previous DP problem, the difficulty lies in finding the state transition equation. Take an example. For example, word1 is “bbc” and word2 is “abcd”. You can get the dp array as follows:
Ø a b c d Ø 0 1 2 3 4 b 1 1 1 2 3 b 2 2 1 2 3 c 3 3 2 1 2
When word1[i] == word2[j], dp[i][j] = dp[i-1][j-1], in other cases, dp[i][j] is its left and upper left, The minimum value of the three values above is increased by 1. In fact, the left, top, and top left here correspond to the addition, deletion, and modification operations respectively. For details, please refer to the explanation part of the first solution, then the state transition equation can be obtained as
dp[i][j] = / dp[i - 1][j - 1] if word1[i - 1] == word2[j - 1] \ min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 else