题解 | 计算字符串的编辑距离

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let cnt = 0;
const input: string[] = [];

rl.on("line", function (line) {
    input.push(line);
    cnt++;
});

rl.on("close", function () {
    const [A, B] = input;

    console.log(minDistance(A, B));
});

function minDistance(strA: string, strB: string) {
  const lenA = strA.length;
  const lenB = strB.length;

  // 字符串相等时编辑距离为 0
  if (strA === strB) {
    return 0;
  }

  // 某个字符串长度为 0 时，编辑距离为另一个字符串长度
  if (lenA * lenB === 0) {
    return lenA + lenB;
  }

  const dp: number[][] = [];

  for (let i = 0; i <= lenA; i++) {
    dp[i] = new Array(lenB).fill(0)
    for (let j = 0; j <= lenB; j++) {
      if (i * j) {
        dp[i][j] =
          strA[i - 1] === strB[j - 1]
            ? dp[i - 1][j - 1]
            : Math.min(
              dp[i - 1][j - 1], // 替换
              dp[i - 1][j], // 插入 B
              dp[i][j - 1], // 插入 A
            ) + 1
      } else {
        dp[i][j] = i + j
      }
    }
  }

  return dp[lenA][lenB]
}