Edit distance

Edit distance is a number quantifying how different are two given strings. It is calculated by counting the minimum number of operations required to transform one string into the other.

In this implementation I assume, that only three operations are available:

  • copy – cost 0
  • insert – cost 1
  • delete – cost 1

Read more on wikipedia.


n a
m b

n, m – length of string
a, b – strings (without spaces, new lines etc.)

Sample input

5 heart
4 head


The algorithm returns a single number, which is the edit distance.


This solution runs in Θ(n · m) time.

Source code