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:

  1. Search for optimal substructure (state representation)
  2. Induction of state transition Equation (State calculation)
  3. 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 toword1Converted toword2The use ofMinimum operand

Then we define dp[I][j] as:

  • When the length of the string word1 isi, 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

    1. Replace word1[I] with word2[j],replaceThe operation takes one step
    • dp[i][j] = dp[i-1][j-1] + 1
    1. If word1[I] is too many, delete it and add one stepdeleteoperation
    • dp[i][j] = dp[i-1][j] + 1
    1. Word1 [I] is missing and needs to be at the end of word1insertA character equal to word2[j]
    • dp[i][j] = dp[i][j-1] + 1

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

reference