logo CodeStepByStep logo

Main Page → Exercises → PHP → Solve an Exercise

edit_distance

Language/Type: PHP recursion string return

Write a recursive function named edit_distance 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
edit_distance("driving", "diving") 1
edit_distance("debate", "irate") 3
edit_distance("football", "cookies") 6

Constraints:

  • Do not declare any global variables.
  • Do not use any loops; you must use recursion.
  • Do not use any auxiliary data structures (e.g. arrays) to this problem.
  • You can declare as many primitive variables (e.g. integers) as you like.
  • You are allowed to define other "helper" functions if you like; they are subject to these same constraints.
Function: Write a PHP 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.