Delete Operation for Two Strings

Description

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:

1. The length of given words won't exceed 500.
2. Characters in given words can only be lower-case letters.

Solution(javascript)

/*
 * @lc app=leetcode id=583 lang=javascript
 *
 * [583] Delete Operation for Two Strings
 */

// @lc code=start
// /** 如何转成循环？ TLE 把字符串放到参数里肯定就没法优化了
//  * @param {string} word1
//  * @param {string} word2
//  * @return {number}
//  */
// const minDistance = function (word1, word2) {
//   const aux = (index, str1, str2) => {
//     if (index >= word1.length && index >= word2.length) {
//       return str1 === str2 ? 0 : Infinity
//     }
//     const a = word1[index] || ''
//     const b = word2[index] || ''
//     return Math.min(
//       aux(index + 1, str1 + a, str2 + b),
//       aux(index + 1, str1, str2 + b) + 1,
//       aux(index + 1, str1 + a, str2) + 1,
//       aux(index + 1, str1, str2) + 2,
//     )
//   }
//   return aux(0, '', '')
// }

// /** Top-down O(n^2)
//  * @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 - 1) {
//       return word2.length - index2
//     }
//     if (index2 > word2.length - 1) {
//       return word1.length - index1
//     }
//     if (word1[index1] === word2[index2]) {
//       memo[key] = aux(index1 + 1, index2 + 1)
//     } else {
//       memo[key] = Math.min(
//         aux(index1 + 1, index2) + 1,
//         aux(index1, index2 + 1) + 1,
//       )
//     }
//     return memo[key]
//   }
//   return aux(0, 0)
// }

// /** Bottom-up O(n^2) Time O(n^2) Space
//  * @param {string} word1
//  * @param {string} word2
//  * @return {number}
//  */
// const minDistance = function (word1, word2) {
//   if (!word1.length || !word2.length) {
//     return word1.length || word2.length
//   }
//   const memo = new Array(word1.length + 1).fill(0).map(() => new Array(word2.length + 1).fill(0))
//   for (let i = 0; i < word1.length; i++) {
//     memo[i][word2.length] = word1.length - i
//   }
//   for (let i = 0; i < word2.length; i++) {
//     memo[word1.length][i] = word2.length - i
//   }
//   for (let index1 = word1.length - 1; index1 >= 0; index1--) {
//     for (let index2 = word2.length - 1; index2 >= 0; index2--) {
//       if (word1[index1] === word2[index2]) {
//         memo[index1][index2] += memo[index1 + 1][index2 + 1]
//       } else {
//         memo[index1][index2] += Math.min(
//           memo[index1 + 1][index2] + 1,
//           memo[index1][index2 + 1] + 1,
//         )
//       }
//     }
//   }
//   return memo[0][0]
// }


// /** Bottom-up O(n^2) Time O(n^2) Space
//  * @param {string} word1
//  * @param {string} word2
//  * @return {number}
//  */
// const minDistance = function (word1, word2) {
//   if (!word1.length || !word2.length) {
//     return word1.length || word2.length
//   }
//   const memo = new Array(word1.length + 1).fill(0).map(() => new Array(word2.length + 1).fill(0))
//   for (let i = 0; i < word1.length; i++) {
//     memo[i][word2.length] = word1.length - i
//   }
//   for (let i = 0; i < word2.length; i++) {
//     memo[word1.length][i] = word2.length - i
//   }
//   for (let index1 = word1.length - 1; index1 >= 0; index1--) {
//     for (let index2 = word2.length - 1; index2 >= 0; index2--) {
//       if (word1[index1] === word2[index2]) {
//         memo[index1][index2] += memo[index1 + 1][index2 + 1]
//       } else {
//         memo[index1][index2] += Math.min(
//           memo[index1 + 1][index2] + 1,
//           memo[index1][index2 + 1] + 1,
//         )
//       }
//     }
//   }
//   return memo[0][0]
// }

/** Bottom-up O(n^2) Time O(n) Space
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
const minDistance = function (word1, word2) {
  if (!word1.length || !word2.length) {
    return word1.length || word2.length
  }

  let prev = 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--) {
      if (index1 === word1.length) {
        current[index2] = word2.length - index2
      } else if (index2 === word2.length) {
        current[index2] = word1.length - index1
      } else if (word1[index1] === word2[index2]) {
        current[index2] += prev[index2 + 1]
      } else {
        current[index2] += Math.min(
          prev[index2] + 1,
          current[index2 + 1] + 1,
        )
      }
    }
    prev = current
  }
  return prev[0]
}
// @lc code=end