506. Edit Distance
Given two strings, print the fewest single-character edits needed to turn the first into the second. An edit is an insertion, a deletion, or a replacement.
The same grid as the previous problem, with a minimum instead of a maximum and a cost instead of a credit. Each neighbour is one edit, chosen by which string it consumes: deleting takes one character of the first, so it is the cell above; inserting matches a character of the second, so it is the cell to the left; replacing consumes one of each, so it is the diagonal.
When the characters already match, take the diagonal at NO cost. That fourth case is the one people forget, and without it the answer is simply the length difference.
Constraints - `1 ≤ length of each string ≤ 500` - Both strings contain lowercase English letters only.
Input
The first line contains the first string. The second line contains the second string.
Output
Print one integer: the fewest edits needed to turn the first string into the second.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.