Good morning! Here's our prompt for today.
The Edit Distance Challenge
What's the Challenge?
Your task is to find the Edit Distance between two strings. The edit distance measures how different two strings are by calculating the minimum number of transformations required to convert one string into another. The allowed transformations are:
- Insertion: Adding a character.
- Deletion: Removing a character.
- Substitution: Replacing one character with another.
For instance, if the two strings are identical, such as cat
and cat
, the edit distance is 0
. That's because no transformations are needed to make the two strings the same.
An Example to Illuminate
Consider two strings mitten
and sitting
. If we call getEditDistance('mitten', 'sitting')
, the function should return 3
. Here's how we arrive at this number:
- mitten → sitten: Substitute "s" for "m."
- sitten → sittin: Substitute "i" for "e."
- sittin → sitting: Insert "g" at the end.
Method Signature
You are to implement a function called getEditDistance(a, b)
that will return the edit distance between strings a
and b
.
1function getEditDistance(a, b) {
2 // Your code here
3}
Constraints to Keep in Mind
- The lengths of both given strings
a
andb
will be less than or equal to1000
. - The answer will fit within the integer range.
- You are only allowed to change one of the strings.
- Let
m
andn
be the lengths ofa
andb
, respectively. - Time Complexity:
O(n * m)
- Space Complexity:
O(n * m)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
console.log('PASSED: ' + "getEditDistance('busa', 'ebcar') should return 4");
var assert = require('assert');
​
function getEditDistance(a, b) {
return '';
}
​
class Graph {
constructor() {
this.adjacencyList = new Map();
this.verticesCount = 0;
}
​
addVertex(nodeVal) {
this.adjacencyList.set(nodeVal, []);
this.verticesCount++;
}
​
addEdge(src, dest) {
this.adjacencyList.get(src).push(dest);
this.adjacencyList.get(dest).push(src);
// push to both adjacency lists
}
​
removeVertex(val) {
if (this.adjacencyList.get(val)) {
this.adjacencyList.delete(val);
}
​
this.adjacencyList.forEach((vertex) => {
Here's how we would solve this problem...
How do I use this guide?