You are given two strings a and b. In one edit you may:
- insert a single character anywhere in the current string,
- delete a single character from the current string, or
- substitute one character for a different character.
Compute the minimum number of edits required to transform a into b. This value is symmetric and is uniquely determined by the two strings.
Input format
Line 1: the string a.
Line 2: the string b.
Either string may be empty (an empty line). Strings consist of printable characters with no leading or trailing spaces and contain no spaces internally.
Output format
A single integer: the minimum number of insert/delete/substitute edits to transform a into b.
Constraints
- 0 ≤ length of
a≤ 2000 - 0 ≤ length of
b≤ 2000 - Characters are compared case-sensitively.