Compute the Levenshtein edit distance
Given exactly two ASCII strings of length at most 500, return the minimum insertions, deletions, and substitutions needed to transform the first into the second. Inputs are valid JSON and must not be modified unless the algorithm uses a local copy. This exercise probes typed data modeling, boundary handling, and algorithm selection.
Input
One JSON value: string[]. See the sample for its exact shape.
Output
One compact JSON value of type number. Strings include JSON quotes; arrays preserve the specified order.
Constraints
Array/string lengths are 0 to 10000 unless stated otherwise. Numbers are integers in [-1000000,1000000]; all computed results fit the safe integer range.
Example
Input
["kitten","sitting"]
Output
3
Example 2 input
["ab","ba"]
Output
2
Checks a boundary or contrasting case beyond the public examples.
Public test cases (2)
Input
["kitten","sitting"]
Expected output
3
Input
["",""]
Expected output
0
Hints (2)
- Start with the required output order and the empty-input behavior.
- Use the prefix edit-distance recurrence with one previous row
Target complexity: time O(n*m) · space O(m)