1172. Edit Distance (Levenshtein)

Given two strings a and b, return the minimum number of single-character insertions, deletions, or substitutions to transform a into b. The input is JSON {a, b}.

Input: JSON {a, b}.

Output: Integer — the edit distance.

Examples

Input: {"a":"horse","b":"ros"}
Output: 3
Explanation: Three edits.

Input: {"a":"intention","b":"execution"}
Output: 5
Explanation: Five edits.

Input: {"a":"","b":"abc"}
Output: 3
Explanation: Three insertions.

Constraints

• 0<=|a|,|b|<=1000

Asked by