Minimum Edit Distance

Minimum Edit Distance

Given two strings A and B, your task is to compute the minimum number of operations required to transform A into B. The allowed operations are insertion, deletion, and substitution. In other words, find the edit distance between the two strings, denoted by $$d(A,B)$$.

For example, transforming "kitten" into "sitting" requires 3 operations, and transforming "flaw" into "lawn" requires 2 operations.

inputFormat

The input is provided from standard input (stdin) and consists of two lines. The first line contains the string A and the second line contains the string B.

outputFormat

Print to standard output (stdout) a single integer representing the minimum number of operations required to transform string A into string B.

kitten
sitting

3