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
horseros3Example 2
intentionexecution5Example 3
abcabc0Use 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]