Minimum Number of Operations needed.

Question

Hello everyone there... I have a problem, suppose I have a given string: "best", the target string is suppose: "beast". Then I have to determine the number of operations to convert the given string to the target string, however the operations allowed are: 1. add a character to string. 2. delete a character. 3. swap two char positions. (should be used wisely, we have only one chance to swap.)

In above case it is 1. How do we solve such kind of problem, and what kind of problem is it? I am a newbie learner.

Answer 1

Levenshtein distance

Answer 2

One widely-used measure of this kind of thing is called the Levenshtein distance.

http://en.wikipedia.org/wiki/Levenshtein%5Fdistance

The WP page also mentions/links to other similar concepts. It is essentially a metric of the number of edits needed to turn one word into another.