An autocorrect engine measures how far a typed word is from a dictionary word by counting the minimum number of single-character edits needed to turn one into the other. An edit is one of: insert a character, delete a character, or replace a character with another. Given the typed word a and the target word b, output this minimum number of edits.
Input format
Line 1: the typed word a.
Line 2: the target word b.
Output format
A single integer: the minimum number of edits to transform a into b.
Constraints
- 1 <= length of
a<= 40 - 1 <= length of
b<= 40 - Both strings consist of lowercase English letters only.