JavaScriptHardDynamic Programming35 min
Compute the Levenshtein edit distance
Return the minimum number of single-character insertions, deletions and substitutions needed to transform the first string into the second. Each operation costs one. All input is valid JSON satisfying the constraints; do not mutate the meaning of values through type coercion. Interviewers use this problem to assess use prefix dynamic programming with only two rows.
Input
A JSON array [firstString, secondString] of ASCII strings.
Output
Print one compact JSON value: an integer distance.
Constraints
Each string has length <= 500.
Example
Input
["kitten","sitting"]
Output
3
Example 2 input
["ab","ba"]
Output
2
Boundary case: Swapping two adjacent characters is not a single allowed operation
Public test cases (2)
Input
["kitten","sitting"]
Expected output
3
Input
["horse","ros"]
Expected output
3
Hints (2)
- Consider the last edit: insert, delete or substitute
- Swapping two adjacent characters is not a single allowed operation
Target complexity: time O((n+1)(m+1)) · space O(min(n,m)+1)