logo CodeStepByStep logo

editDistance

Language/Type: Kotlin recursion string return
Related Links:

Write a recursive function named editDistance that accepts string parameters s1 and s2 and returns the "edit distance" between the two strings as an integer. Edit distance (also called Levenshtein distance) is defined as the minimum number of "changes" required to get from s1 to s2 or vice versa. A "change" can be defined as a) inserting a character, b) deleting a character, or c) changing a character to a different character.

Call Value Returned
editDistance("driving", "diving") 1
editDistance("debate", "irate") 3
editDistance("football", "cookies") 6

Constraints: Your solution must obey the following constraints:

  • Your solution must not use any loops it must be recursive.
  • Strings have member functions named indexOf, but you should not call them, because they allow you to get around using recursion. Similarly, the replace and replaceAll members are forbidden.
  • Do not construct any data structures (no array, list, set, map, etc.), and do not declare any global variables. You are allowed to define other "helper" functions if you like.
Type your Kotlin solution code here:


This is a function exercise. Write a Kotlin function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

Need help?

If you do not understand how to solve an exercise or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect tests, etc.), please

Is there a problem? Contact a site administrator.

©, all rights reserved.