Saturday 15 May 2010

c - Minimum Number of Operations needed -


I have a problem, suppose I have the string given: "best", the target string assumes: "animal" . So I have to set the number of operations to convert the defined string to the target string, though the action is allowed: 1. Add a character for the string. 2. Remove a character. 3. Swap two or four posts (should be used wisely, we have a chance to swap.)

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

The widely used method of this kind is called Levenshtein Distance.

The WP page also mentions / links other similar concepts. This is essentially a metric of the number of edits required to replace one word in one word.


No comments:

Post a Comment