Edit Distance

Description

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character
2. Delete a character
3. 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')

Solution(javascript)

/*
 * @lc app=leetcode id=72 lang=javascript
 *
 * [72] Edit Distance
 */

// @lc code=start
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

// recursive
// const minDistance = (word1 = '', word2 = '') => {
//   const memo = new Array(word1.length).fill(0).map(() => new Array(word2.length).fill(undefined))

//   const aux = (index1, index2) => {
//     if (memo[index1][index2] !== undefined) {
//       return memo[index1][index2]
//     }
//     if (index1 <= -1) {
//       return index2 + 1
//     }
//     if (index2 <= -1) {
//       return index1 + 1
//     }
//     if (word1[index1] === word2[index2]) {
//       memo[index1][index2] = aux(index1 - 1, index2 - 1)
//       return memo[index1][index2]
//     }
//     memo[index1][index2] = 1 + Math.min(
//       aux(index1, index2 - 1),
//       aux(index1 - 1, index2 - 1),
//       aux(index1 - 1, index2),
//     )
//     return memo[index1][index2]
//   }
//   return aux(word1.length - 1, word2.length - 1)
// }


// /** 1: Top-down Approach
//  * @param {string} word1
//  * @param {string} word2
//  * @return {number}
//  */
// const minDistance = function (word1, word2) {
//   const memo = {}
//   const aux = (index1, index2) => {
//     const key = `${index1}-${index2}`
//     if (memo[key] !== undefined) {
//       return memo[key]
//     }
//     if (index1 >= word1.length) {
//       return word2.length - index2
//     }
//     if (index2 >= word2.length) {
//       return word1.length - index1
//     }
//     const a = word1[index1]
//     const b = word2[index2]
//     if (a === b) {
//       memo[key] = aux(index1 + 1, index2 + 1)
//     } else {
//       memo[key] = Math.min(
//         aux(index1 + 1, index2),
//         aux(index1, index2 + 1),
//         aux(index1 + 1, index2 + 1),
//       ) + 1
//     }
//     return memo[key]
//   }
//   return aux(0, 0)
// }

/** 2: Bottom-up Approach
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
const minDistance = function (word1, word2) {
  let memo = new Array(word2.length + 1).fill(0)
  for (let index1 = word1.length; index1 >= 0; index1--) {
    const current = new Array(word2.length + 1).fill(0)
    for (let index2 = word2.length; index2 >= 0; index2--) {
      const a = word1[index1]
      const b = word2[index2]

      if (index1 === word1.length) {
        current[index2] = word2.length - index2
      } else if (index2 === word2.length) {
        current[index2] = word1.length - index1
      } else if (a === b) {
        current[index2] += memo[index2 + 1]
      } else {
        current[index2] += Math.min(
          memo[index2],
          current[index2 + 1],
          memo[index2 + 1],
        ) + 1
      }
    }
    memo = current
  }
  return memo[0]
}
// @lc code=end