演算法

1function editDistance(textA: string, textB: string): number[][] {
2  const a = Array.from(textA), b = Array.from(textB);
3  const d: number[][] = [];
4  for (let i = 0; i <= a.length; i++) {
5    d.push(new Array(b.length + 1).fill(0));
6    for (let j = 0; j <= b.length; j++) {
7      if (i === 0 || j === 0) {
8        d[i][j] = i + j;
9        continue;
10      }
11      const same = a[i - 1] === b[j - 1];
12      const diagonal = d[i - 1][j - 1] + (same ? 0 : 1);
13      const up = d[i - 1][j] + 1;
14      const left = d[i][j - 1] + 1;
15      d[i][j] = Math.min(diagonal, up, left);
16    }
17  }
18  return d;
19}
20 
21function editScript(textA: string, textB: string, d: number[][]): string[] {
22  const a = Array.from(textA), b = Array.from(textB);
23  const ops: string[] = [];
24  let i = a.length, j = b.length;
25  while (i > 0 || j > 0) {
26    const same = i > 0 && j > 0 && a[i - 1] === b[j - 1];
27    if (i > 0 && j > 0 && d[i][j] === d[i - 1][j - 1] + (same ? 0 : 1)) {
28      ops.push(same ? "keep" : "substitute");
29      i--;
30      j--;
31    } else if (i > 0 && d[i][j] === d[i - 1][j] + 1) {
32      ops.push("delete");
33      i--;
34    } else {
35      ops.push("insert");
36      j--;
37    }
38  }
39  return ops.reverse();
40}