String Dynamic Programming Tabulation
Guru Level

Implement the editDistanceSimple method that returns the minimum edit operations needed to convert one string into another.

The input contains two strings, first and second. Your task is to return the minimum number of operations needed to convert the first string into the second string.

The allowed operations are insert a character, delete a character, or replace a character. For example, converting horse to ros takes 3 operations.

Example 1
Input:
first (string) = horse
second (string) = ros
Return:
(int) 3
Example 2
Input:
first (string) = intention
second (string) = execution
Return:
(int) 5
Example 3
Input:
first (string) = abc
second (string) = abc
Return:
(int) 0

Use dynamic programming to compare prefixes of both strings.

Let dp[i][j] store the minimum operations needed to convert the first i characters of first into the first j characters of second.

If the current characters are equal, no new operation is needed. Otherwise, choose the best among insert, delete, and replace, then add one operation.

Pseudocode:

function editDistanceSimple(first, second):
    n = length(first)
    m = length(second)
    dp = 2D array of size (n + 1) x (m + 1)
    for i from 0 to n:
        dp[i][0] = i
    for j from 0 to m:
        dp[0][j] = j
    for i from 1 to n:
        for j from 1 to m:
            if first[i - 1] == second[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                insertCost = dp[i][j - 1]
                deleteCost = dp[i - 1][j]
                replaceCost = dp[i - 1][j - 1]
                dp[i][j] = 1 + min(insertCost, deleteCost, replaceCost)
    return dp[n][m]
Run your code to see the result.