Description
Problem Introduction
The edit distance between 2 strings is the minimum number of operations (insertions, deletions, and substitutions of symbols) to transform 1 string into another.
It is a measure of similarity of two strings.
Edit distance has applications, for example, in computational biology, natural language processing, and spell checking. Your goal in this problem is to compute the edit distance between two strings.
Problem Description
Task.
The goal of this problem is to implement the algorithm for computing the edit distance between 2 strings.
Input Format.
Each of the 2 lines of the input contains a string consisting of lower case latin letters.
Constraints.
The length of both strings is at least 1 and at most 100.
Output Format.
Output the edit distance between the given 2 strings.
E.g. 1.
Input:
ab
ab
Output: 0
E.g. 2.
Input:
short
ports
Output: 3
An alignment of total cost 3:
s h o r t −
− p o r t s
E.g. 3,
Input:
editing
distance
Output: 5
An alignment of total cost 5:
e d i − t i n g −
− d i s t a n c e