Question
Autocorrect Repair Cost
A typing assistant receives a wrong word and wants to convert it into the intended word. In one operation, it can insert one character, delete one character, or replace one character.
Find the minimum number of operations required.
The twist: sometimes replacing is not best; deleting now and matching later can be cheaper.
Input
The first line contains the typed word KaTeX can only parse string typed expression.
The second line contains the intended word KaTeX can only parse string typed expression.
Output
Print a single integer — the minimum number of operations required to convert KaTeX can only parse string typed expression into KaTeX can only parse string typed expression.
Example
Example 1:
Input
Example 2:
Input
Input
horse
ros3Example 2:
Input
intention
execution5