String Dynamic Programming Recursion
Guru Level

Implement the method editDistance that returns the minimum number of edits needed to convert one string into another.

Allowed edits are insert one character, delete one character, or replace one character.

The task is designed to test careful handling of edge cases, not only the most common input.

  • Each edit costs 1.
  • Return 0 if the strings are already equal.
  • The whole source string must be converted into the whole target string.
Example 1
Input:
word1 (string) = horse
word2 (string) = ros
Return:
(int) 3
Example 2
Input:
word1 (string) = intention
word2 (string) = execution
Return:
(int) 5
Example 3
Input:
word1 (string) = abc
word2 (string) = abc
Return:
(int) 0

Use a dynamic programming table where dp[i][j] is the best answer for the first i and j characters.

Run your code to see the result.