Solving Edit Distance using Dynamic Programming

Let’s look into another popular dynamic programming coding interview question on Strings.

Problem Statement

The “Edit Distance” problem is described as follows:

Given two strings word1 and word2, we need to determine the minimum number of operations (insertions, deletions, or substitutions of a character) required to convert word1 to word2.

Understanding The Problem

Consider the example of changing “horse” to “ros”.

We need 3 operations:

horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

This problem is a classic example of Dynamic Programming (DP), but before we get to that, let’s start with a simple brute force solution.

Brute Force Solution

We start from the beginning of both strings. At each step, we have three options: replace the current character, delete it, or insert a character.

Let’s code this brute force solution in Java:

class Solution {
    public int minDistance(String word1, String word2) {
        return calculate(word1, word2, 0, 0);
    }

    private int calculate(String word1…