logo CodeStepByStep logo

Main Page → Exercises → JavaScript → Solve an Exercise

editDistance

Language/Type: JavaScript recursion string

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

  1. inserting a character,
  2. deleting a character, or
  3. changing a character to a different character.
Below are example calls of your function and expected return values:

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

Constraints:

  • Your solution must not use any loops; it must be recursive.
  • Do not construct any arrays and do not declare any global variables.
  • You are allowed to define other "helper" functions if you like.

Function: Write a JavaScript function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.