72-编辑距离.md

72-编辑距离

原题

给你两个单词  word1 和  word2， 请返回将  word1  转换成  word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

插入一个字符 删除一个字符 替换一个字符

输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

其实我觉得这道题目到是很有意思，感觉应该在日常变成中也会有用到的 解法参考

const minDistance = (s1, s2) => {
  const dp = (i, j) => {
    if (i === -1) {
      return j + 1;
    }
    if (j === -1) {
      return i + 1;
    }

    if (s1[i] === s2[j]) {
      return dp(i - 1, j - 1); // 啥都不做
    } else {
      return Math.min(
        dp(i, j - 1) + 1, // 插入
        dp(i - 1, j) + 1, // 删除
        dp(i - 1, j - 1) + 1 // 替换
      );
    }
  };

  // i，j 初始化指向最后一个索引
  return dp(s1.length - 1, s2.length - 1);
};

let result = minDistance('horse', 'ros');
console.log(result);