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) =
horsesecond (string) =
rosReturns (int)
3Example 2
Input
first (string) =
intentionsecond (string) =
executionReturns (int)
5Example 3
Input
first (string) =
abcsecond (string) =
abcReturns (int)
0Use 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run