Good afternoon! Here's our prompt for today.
Can you determine the deletion distance between two strings? Let's define the deletion distance as the numbers of characters needed to delete from two strings to make them equal.

For example, the deletion distance of algo
and daily
is 5. The reason is we can delete the go
(2 deletion) in algo
, and the d
, i
and y
(3 deletions) in daily
.
Constraints
- Length of both the strings <=
1000
- The strings can be empty
- Take into consideration all the ASCII characters
- Let
m
andn
be the the lengths ofstring 1
andstring 2
- Expected time complexity
O(m*n)
- Expected space complexity :
O(m*n)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
127
console.log('PASSED: ' + "deletionDistance('some', 'thing') should return 9");
var assert = require('assert');
​
function deletionDistance(str1, str2) {
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) => {
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
We'll now take you through what you need to know.
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.