This is the 4th day of my participation in the August More Text Challenge
This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.
147. Edit-distance
The label
- Dynamic programming
- difficult
The title
Leetcode portal
Given two words word1 and word2, please calculate the minimum operand needed to convert word1 into word2
You can do one of three things with a word:
- Insert a character
- Delete a character
- Replace a character
Example 1
Enter: word1 ="horse", word2 = "ros"Output:3Explanation: horse -> rorse (will'h'Replace with'r') rorse -> rose (delete'r') rose -> ros (delete'e')
Copy the code
Example 2
Enter: word1 ="intention", word2 = "execution"Output:5Intention -> inention't') inention -> enention'i'Replace with'e') enention -> exention'n'Replace with'x') exention -> exection'n'Replace with'c') exection -> execution'u')
Copy the code
The basic idea
Encountered this kind of optimal problem, or think of using moving gauge method to solve. Our general steps before were the following:
- Search for optimal substructure (state representation)
- Induction of state transition Equation (State calculation)
- Boundary initialization
1. Status representation
The first is the state representation. The focus is the target of the question. From the target, we find the variables that need to be represented
- Goal is to
word1
Converted toword2
The use ofMinimum operand
Then we define dp[I][j] as:
- When the length of the string word1 is
i
, the length of the string word2 isj
, convert word1 to that used by word2Minimum number of operationsfordp[i][j]
.
2. Status transfer
This step is sometimes very difficult to think about, need to see, think about
Here is a trick is commonly dp [I] [j] are with dp [I – 1] [1] / dp [j] / [I – 1] dp [I] [1] / transfer relationship exists. Then take the maximum and minimum values of each.
To review our goal, we want to convert word1 to word2 to find the minimum number of operands used
If word1[I] is the same as word2[j], do not change, then
dp[i][j] = dp[i-1][j-1]
We need to think about the following three modifications
-
- Replace word1[I] with word2[j],
replace
The operation takes one step
dp[i][j] = dp[i-1][j-1] + 1
- Replace word1[I] with word2[j],
-
- If word1[I] is too many, delete it and add one step
delete
operation
dp[i][j] = dp[i-1][j] + 1
- If word1[I] is too many, delete it and add one step
-
- Word1 [I] is missing and needs to be at the end of word1
insert
A character equal to word2[j]
dp[i][j] = dp[i][j-1] + 1
- Word1 [I] is missing and needs to be at the end of word1
And the optimal case, which is to minimize dp[I][j], can be derived
dp[i][j] = Math.min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
Copy the code
3. Initialize the boundary
And the general boundary starts at 0
Let’s think about what I === = 0 or j === 0 means, as long as one of them is 0, then the conversion process is actually very simple, either add or subtract, then
dp[0][j] = dp[0][j-1] + 1 // Keep adding
dp[i][0] = dp[i-1] [0] + 1 // Keep deleting
Copy the code
Well, after these three steps, our code is ready to go. Here’s the implementation
Writing implement
var minDistance = function(word1, word2) {
const n1 = word1.length, n2 = word2.length
let dp = new Array(n1+1).fill(0).map(it= > new Array(n2+1).fill(0))
// console.log(dp)
/ / /
// [0, 0, 0, 0]
// [0, 0, 0, 0]
// [0, 0, 0, 0]
// [0, 0, 0, 0]
// [0, 0, 0, 0]
// [0, 0, 0, 0]
// ]
When one string goes to 0, the other string can only be inserted or deleted, i.e. + 1
for (let i = 1; i <= n1; i++) {
dp[i][0] = dp[i-1] [0] + 1
}
for (let j = 1; j <= n2; j++) {
dp[0][j] = dp[0][j-1] + 1
}
// console.log(dp)
/ / /
// [0, 1, 2, 3],
// [1, 0, 0, 0],
// [2, 0, 0, 0],
// [3, 0, 0, 0],
// [4, 0, 0, 0],
// [5, 0, 0, 0]
// ]
for (let i = 1; i <= n1; i++) {
for (let j = 1; j <= n2; j++) {
if (word1[i-1] === word2[j-1]) {
// When characters are the same, no operation is required
dp[i][j] = dp[i-1][j-1]}else {
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1}}}// console.log(dp)
/ / /
// [0, 1, 2, 3],
// [1, 1, 2, 3],
// [2, 2, 1, 2]
// [3, 2, 2, 2],
// [4, 3, 3, 2],
// [5, 4, 4, 3]
// ]
// The bottom right corner is the result, the minimum edit distance
return dp[n1][n2]
};
let word1 = "horse", word2 = "ros" / / 3
console.log(minDistance(word1, word2))
Copy the code
Optimization algorithm
We’re thinking, well, we’re actually doing this row by row, which is counting the ith row, but it’s really just related to the ith minus 1 row
Let me draw a simple picture
/ / dp is a two dimensional array [(j - I - 1, 1) (I - 1, j) (I, j - 1) (I, j)]Copy the code
In fact, each calculation of dp[I][j] is only related to these numbers. After we calculate the next row, we can erase the previous row, modify in place, reduce the dimension to a one-dimensional array, and look at the code
var minDistance = function(word1, word2) {
let n1 = word1.length, n2 = word2.length
let dp = new Array(n2+1).fill(0)
for (let j = 1; j <= n2; j++) {
dp[j] = j
}
// console.log(dp)
// dp: [ 0, 1, 2, 3 ]
// The first row (I =0) is dp
// The next row is derived from the previous row
for (let i = 1; i <= n1; i++) {
// dp[0] = dp[i-1] = j-1
let temp = dp[0]
dp[0] = i
for (let j = 1; j <= n2; j++) {
let pre = temp
temp = dp[j]
if (word1[i-1] === word2[j-1]) {
dp[j] = pre
} else {
dp[j] = Math.min(dp[j-1], dp[j], pre) + 1}}}// console.log(dp)
// dp: [ 5, 4, 4, 3 ]
// The last line (I =n1) is dp
return dp[n2]
};
let word1 = "horse", word2 = "ros" / / 3
console.log(minDistance(word1, word2))
Copy the code
In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series
If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions