72. Edit Distance

原题：72. Edit Distance

source code

// Runtime: 100 ms, faster than 57.51% of JavaScript online submissions for Edit Distance.
// Memory Usage: 40.7 MB, less than 50.00% of JavaScript online submissions for Edit Distance.
var minDistance = function (word1, word2) {
  //注意这里创建的长度是(word1.length+1)*(word2.length+1)，因为word1、word2可能是空串，因此i/j实际表示的是子串的长度（从index 0开始）
  //因此dp[i][j]表示word1[i-1]演变到word2[j-1]最少需要的操作数
  const dp = new Array(word1.length + 1)
    .fill(0)
    .map((v) => new Array(word2.length + 1).fill(0));
  for (let i = 0; i <= word1.length; i++) {
    //从word1[i]演变到word2[0]，只能删除i个字符
    dp[i][0] = i;
  }

  for (let j = 0; j <= word2.length; j++) {
    //从word1[0]演变成word2[j]，只能新增j个字符
    dp[0][j] = j;
  }

  for (let i = 1; i <= word1.length; i++) {
    for (let j = 1; j <= word2.length; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        //三种操作：
        //insert: dp[i][j - 1]; 因为word1[i]只能演变成word2[j-1]，因此如果要演变成word2[j]，需要插入一个字符（word2中索引为j-1的字符）
        //remove: dp[i - 1][j]; 因为word1[i-1]已经成演变成[j]，因此需要移除word1索引为i-1的字符
        //replace: dp[i - 1][j - 1];
        dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
      }
    }
  }

  return dp[word1.length][word2.length];
};

test cases

test("test1", () => {
  expect(minDistance("horse", "ros")).toEqual(3);
});
// horse -> rorse (replace 'h' with 'r')
// rorse -> rose (remove 'r')
// rose -> ros (remove 'e')

test("test2", () => {
  expect(minDistance("intention", "execution")).toEqual(5);
});
// 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')

test("test3", () => {
  expect(minDistance("a", "a")).toEqual(0);
});

test("test4", () => {
  expect(minDistance("", "a")).toEqual(1);
});

test("test5", () => {
  expect(minDistance("a", "")).toEqual(1);
});