1var assert = require('assert');
2
3function getEditDistance(a, b) {
4  if (a.length == 0) return b.length;
5  if (b.length == 0) return a.length;
6
7  var matrix = [];
8
9  // increment along the first column of each row
10  var i;
11  for (i = 0; i <= b.length; i++) {
12    matrix[i] = [i];
13  }
14
15  // increment each column in the first row
16  var j;
17  for (j = 0; j <= a.length; j++) {
18    matrix[0][j] = j;
19  }
20
21  // Fill in the rest of the matrix
22  for (i = 1; i <= b.length; i++) {
23    for (j = 1; j <= a.length; j++) {
24      if (b.charAt(i - 1) == a.charAt(j - 1)) {
25        matrix[i][j] = matrix[i - 1][j - 1];
26      } else {
27        matrix[i][j] = Math.min(
28          matrix[i - 1][j - 1] + 1, // substitution
29          Math.min(
30            matrix[i][j - 1] + 1, // insertion
31            matrix[i - 1][j] + 1
32          )
33        ); // deletion
34      }
35    }
36  }
37
38  return matrix[b.length][a.length];
39}
40
41class Graph {
42  constructor() {
43    this.adjacencyList = new Map();
44    this.verticesCount = 0;
45  }
46
47  addVertex(nodeVal) {
48    this.adjacencyList.set(nodeVal, []);
49    this.verticesCount++;
50  }
51
52  addEdge(src, dest) {
53    this.adjacencyList.get(src).push(dest);
54    this.adjacencyList.get(dest).push(src);
55    // push to both adjacency lists
56  }
57
58  removeVertex(val) {
59    if (this.adjacencyList.get(val)) {
60      this.adjacencyList.delete(val);
61    }
62
63    this.adjacencyList.forEach((vertex) => {
64      const neighborIdx = vertex.indexOf(val);
65      if (neighborIdx >= 0) {
66        vertex.splice(neighborIdx, 1);
67      }
68    });
69  }
70
71  removeEdge(src, dest) {
72    const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);
73    this.adjacencyList.get(src).splice(srcDestIdx, 1);
74
75    const destSrcIdx = this.adjacencyList.get(dest).indexOf(src);
76    this.adjacencyList.get(dest).splice(destSrcIdx, 1);
77  }
78
79  printNeighbors() {
80    const result = [];
81
82    for (let vertex of this.adjacencyList.keys()) {
83      const neighbors = [];
84
85      neighbors.push(`${vertex}:`);
86
87      this.adjacencyList.get(vertex).forEach((neighbor) => {
88        neighbors.push(neighbor);
89      });
90
91      result.push(neighbors.join(' '));
92    }
93
94    return result;
95  }
96
97  verticesCount() {
98    return this.verticesCount;
99  }
100
101  reverse() {
102    const graph = new Graph();
103    for (let [src, dests] of this.adjacencyList) {
104      graph.addVertex(src);
105    }
106
107    for (let [src, dests] of this.adjacencyList) {
108      for (let dest of this.adjacencyList.get(src)) {
109        graph.adjacencyList.get(src).push(dest);
110      }
111    }
112
113    return graph;
114  }
115}
116
117var matrix1 = [
118  [1, 1, 0, 0, 0],
119  [0, 1, 1, 0, 0],
120  [0, 1, 0, 1, 0],
121  [1, 0, 0, 0, 0],
122];
123
124var matrix2 = [
125  [1, 1, 0, 0],
126  [0, 0, 1, 0],
127  [0, 1, 1, 0],
128  [1, 0, 0, 0],
129];
130
131var planeMatrix1 = [
132  ['.', '.', '.', 'P'],
133  ['.', '.', '.', 'P'],
134  ['P', 'P', '.', 'P'],
135  ['.', '.', '.', 'P'],
136];
137
138try {
139  assert.deepEqual(getEditDistance('busa', 'ebcar'), 4);
140
141  console.log('PASSED: ' + "getEditDistance('busa', 'ebcar') should return 4");
142} catch (err) {
143  console.log(err);
144}
145
146try {
147  assert.deepEqual(getEditDistance('kimwohe', 'jicwil'), 5);
148
149  console.log(
150    'PASSED: ' + "getEditDistance('kimwohe', 'jicwil') should return 5"
151  );
152} catch (err) {
153  console.log(err);
154}
155
156try {
157  assert.deepEqual(getEditDistance('cegaga', 'ki'), 6);
158
159  console.log('PASSED: ' + "getEditDistance('cegaga', 'ki') should return 6");
160} catch (err) {
161  console.log(err);
162}
163
164try {
165  assert.deepEqual(getEditDistance('fe', 'piw'), 3);
166
167  console.log('PASSED: ' + "getEditDistance('fe', 'piw') should return 3");
168} catch (err) {
169  console.log(err);
170}
171
172try {
173  assert.deepEqual(getEditDistance('lesocareb', 'derubeze'), 7);
174
175  console.log(
176    'PASSED: ' + "getEditDistance('lesocareb', 'derubeze') should return 7"
177  );
178} catch (err) {
179  console.log(err);
180}