Edit Distance or Levenshtein Distance in an Easy Recursion + Memoization Way

Edit Distance, also known as Levenshtein Distance, is a common problem where we need to find the minimum number of operations required to convert one string into another.

The three allowed operations are:

• Insert a character
• Delete a character
• Replace a character

For example:

word1 = "horse"
word2 = "ros"

Output: 3

We can convert "horse" into "ros" using three operations:

1. Replace h with r: "rorse"
2. Delete r: "rose"
3. Delete e: "ros"

Let's solve this problem using recursion + memoization in JavaScript.

Step 1: Initialize the DP matrix

First, initialize a two-dimensional array to store the results of our recursive calls.

var t = [];

for (let i = 0; i <= word1.length; i++) {
    let temp = [];

    for (let j = 0; j <= word2.length; j++) {
        temp.push(-1);
    }

    t.push(temp);
}

Important point: Always initialize the DP matrix with length + 1 rows and columns.

Why?

Our recursive function works with character indices, but it can also reach the end of either string. For example, if the string length is 5, the index can reach 5 when all five characters have been processed.

Therefore, we need indices from 0 to word.length, inclusive.

We initialize every cell with -1 to indicate that the result has not been calculated yet.

Step 2: Construct the recursive function

We'll create a function called editDistance that takes five arguments:

• w1: First string
• w2: Second string
• m: Current index in the first string
• n: Current index in the second string
• t: DP matrix for memoization

The function returns the minimum operations required to convert the remaining part of w1 into the remaining part of w2.

2.1 Handle the base conditions

if (m == w1.length && n == w2.length) {
    t[m][n] = 0;
    return 0;
}

if (m == w1.length) {
    t[m][n] = w2.length - n;
    return t[m][n];
}

if (n == w2.length) {
    t[m][n] = w1.length - m;
    return t[m][n];
}

There are three cases to handle.

Case 1: Both strings have reached their ends

No characters remain, so no operation is required. The answer is 0.

Case 2: The first string has ended

If characters remain in the second string, we need to insert all of them.

For example:

w1 = ""
w2 = "abc"

Operations required = 3

Case 3: The second string has ended

If characters remain in the first string, we need to delete all of them.

w1 = "abc"
w2 = ""

Operations required = 3

2.2 Check whether the result is already calculated

if (t[m][n] != -1) {
    return t[m][n];
}

This is where memoization comes into play.

Before calculating the answer for the current indices, we check whether the DP matrix already contains the result.

If it does, we return the stored value instead of repeating the recursive work.

2.3 If the characters match

if (w1[m] == w2[n]) {
    t[m][n] = editDistance(w1, w2, m + 1, n + 1, t);
    return t[m][n];
}

If the current characters match, we don't need to perform any operation.

We simply move both indices forward and solve the remaining problem.

For example:

w1 = "abc"
w2 = "adc"

Current characters: a and a

They match, so move to the next characters.

Notice that we don't add 1 to the recursive result because no edit operation was required.

2.4 If the characters don't match

This is the most important part of the solution.

When the current characters differ, we have three choices.

1. Replace

Replace the current character in the first string with the current character in the second string.

editDistance(w1, w2, m + 1, n + 1, t)

Both indices move forward because the current characters have been matched through replacement.

2. Insert

Insert the current character from the second string into the first string.

editDistance(w1, w2, m, n + 1, t)

The first index stays the same, while the second index moves forward.

3. Delete

Delete the current character from the first string.

editDistance(w1, w2, m + 1, n, t)

The first index moves forward, while the second index stays the same.

Since we want the minimum number of operations, we take the minimum of these three choices and add 1 for the current operation.

t[m][n] = 1 + Math.min(
    editDistance(w1, w2, m + 1, n + 1, t), // Replace
    editDistance(w1, w2, m, n + 1, t),     // Insert
    editDistance(w1, w2, m + 1, n, t)      // Delete
);

return t[m][n];

Remember this important rule

Whenever you calculate a result for a DP state:

1. Store the result in t[m][n].
2. Return the result.

This ensures that the answer is available for future recursive calls and that the caller receives the correct value.

Step 3: Call the recursive function

We start with both indices at 0, since we want to compare the strings from their first characters.

var minDistance = function(word1, word2) {
    let t = [];

    for (let i = 0; i <= word1.length; i++) {
        let temp = [];

        for (let j = 0; j <= word2.length; j++) {
            temp.push(-1);
        }

        t.push(temp);
    }

    return editDistance(word1, word2, 0, 0, t);
};

The recursive function begins at editDistance(word1, word2, 0, 0, t).

Therefore, t[0][0] stores the answer to the original problem: the minimum number of operations required to convert the entire first string into the second string.

Complete solution

Here is the complete code in one place.

var minDistance = function(word1, word2) {
    let t = [];

    for (let i = 0; i <= word1.length; i++) {
        let temp = [];

        for (let j = 0; j <= word2.length; j++) {
            temp.push(-1);
        }

        t.push(temp);
    }

    return editDistance(word1, word2, 0, 0, t);
};

function editDistance(w1, w2, m, n, t) {
    if (m == w1.length && n == w2.length) {
        t[m][n] = 0;
        return 0;
    }

    if (m == w1.length) {
        t[m][n] = w2.length - n;
        return t[m][n];
    }

    if (n == w2.length) {
        t[m][n] = w1.length - m;
        return t[m][n];
    }

    if (t[m][n] != -1) {
        return t[m][n];
    }

    if (w1[m] == w2[n]) {
        t[m][n] = editDistance(w1, w2, m + 1, n + 1, t);
    } else {
        t[m][n] = 1 + Math.min(
            editDistance(w1, w2, m + 1, n + 1, t),
            editDistance(w1, w2, m, n + 1, t),
            editDistance(w1, w2, m + 1, n, t)
        );
    }

    return t[m][n];
}

Time and space complexity

Let m be the length of word1 and n be the length of word2.

• Time complexity: O(m × n) because each DP state is calculated at most once, and each state performs constant work apart from its recursive calls.
• Space complexity: O(m × n) for the DP matrix, plus O(m + n) worst-case recursion stack space.

Final takeaway

The key to solving this problem is to define what each recursive state represents:

editDistance(w1, w2, m, n, t) returns the minimum operations needed to convert the remaining portion of the first string into the remaining portion of the second string.

Once that is clear, the rest follows naturally:

• If the characters match, move both pointers.
• If they don't match, try insert, delete, and replace.
• Take the minimum cost.
• Store the result and return it.

The most useful habit when writing recursive DP solutions is simple: calculate the answer for a state, store it in the DP matrix, and return it.

That pattern will help you recognize and solve many other recursion + memoization problems.