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:

1. mitten → sitten: Substitute "s" for "m."
2. sitten → sittin: Substitute "i" for "e."
3. 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 and b will be less than or equal to 1000.
• The answer will fit within the integer range.
• You are only allowed to change one of the strings.
• Let m and n be the lengths of a and b, 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 our guided, illustrated walk-through.

How do I use this guide?