Edit Distance Problem

Given two strings A and B, your task is to compute the minimum number of operations required to convert A into B. The allowed operations are:

• Insertion
• Deletion
• Replacement

The edit distance is defined using the following recurrence in ( \LaTeX ):

[ \text{dp}[i][j] = \begin{cases} j, & \text{if } i = 0, \ i, & \text{if } j = 0, \ \text{dp}[i-1][j-1], & \text{if } A_{i} = B_{j}, \ 1 + \min\left{\text{dp}[i-1][j],,\text{dp}[i][j-1],,\text{dp}[i-1][j-1]\right}, & \text{otherwise.} \end{cases} ]

Here, ( A_{i} ) and ( B_{j} ) denote the ( i )-th and ( j )-th characters of ( A ) and ( B ) respectively (considering 1-indexing).

inputFormat

The input is given 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

Output a single integer on standard output (stdout) which denotes the minimum edit distance between string A and string B.## sample

sunday
saturday

3