-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEditDistance.js
More file actions
35 lines (30 loc) · 960 Bytes
/
Copy pathEditDistance.js
File metadata and controls
35 lines (30 loc) · 960 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// https://leetcode-cn.com/problems/edit-distance/
var Test = require('../Common/Test');
var { Matrix } = require('../Common/Matrix');
var minDistance = function (word1, word2) {
const len1 = word1.length + 1;
const len2 = word2.length + 1;
const dp = Array(len2).fill(0).map(a => Array(len1).fill(0));
for (let y = 0; y < len2; y++) {
dp[y][0] = y;
}
for (let x = 0; x < len1; x++) {
dp[0][x] = x;
}
Matrix.logMatrixInArray(dp);
for (let y = 1; y < len2; y++) {
for (let x = 1; x < len1; x++) {
dp[y][x] = Math.min(
dp[y][x - 1] + 1,
dp[y - 1][x] + 1,
dp[y - 1][x - 1] + (word1[x - 1] == word2[y - 1] ? 0 : 1));
}
}
Matrix.logMatrixInArray(dp);
return dp[word2.length][word1.length];
};
function test(word1, word2) {
Test.test(minDistance, word1, word2);
}
test("horse", "ros");
test("intention", "execution");