72.edit-distance.js

/*
 * @lc app=leetcode id=72 lang=javascript
 *
 * [72] Edit Distance
 *
 * https://leetcode.com/problems/edit-distance/description/
 *
 * algorithms
 * Hard (35.58%)
 * Total Accepted:    148.7K
 * Total Submissions: 417.9K
 * Testcase Example:  '"horse"\n"ros"'
 *
 * 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:
 *
 *
 * Insert a character
 * Delete a character
 * 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')
 *
 *
 */
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
function minDistance(word1, word2) {
  const m = word1.length + 1,
        n = word2.length + 1;

  const dp = new Array(m).fill(null)
    .map(_ => new Array(n));

  for (let i = 0; i < m; i++)
    dp[i][0] = i;

  for (let j = 0; j < n; j++)
    dp[0][j] = j;

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = (word1[i - 1] === word2[j - 1])
        ? dp[i - 1][j - 1]
        : Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1;
    }
  }

  return dp[m - 1][n - 1];
};