Array String Dynamic Programming Memoization Tabulation
Guru Level

Implement the editDistanceDpOperations method that returns the minimum edit operations using dynamic programming.

The input contains two strings, first and second. Your task is to find the minimum number of edit operations required to convert first into second.

The allowed operations are insert a character, delete a character, or replace one character with another. Each operation has a cost of 1.

For example, converting horse into ros requires 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 because the answer for longer strings depends on answers for smaller prefixes of the two strings.

Create a table where dp[i][j] stores the minimum operations needed to convert the first i characters of first into the first j characters of second.

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

Pseudocode:

function editDistanceDpOperations(first, second):
    m = length of first
    n = length of second
    create dp table of size (m + 1) x (n + 1)
    for i from 0 to m:
        dp[i][0] = i
    for j from 0 to n:
        dp[0][j] = j
    for i from 1 to m:
        for j from 1 to n:
            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 + minimum(insertCost, deleteCost, replaceCost)
    return dp[m][n]
Run your code to see the result.