PythonHardDynamic Programming35 min
Compute the minimum edit distance
Allowed edits are insertion, deletion and substitution, each with cost one. Characters are compared exactly and either string may be empty. Interviewers use this problem to assess build prefix distances and retain only the previous row.
Input
Two lines: source string and target string.
Output
Print the result on one line; print an empty line for an empty string.
Constraints
0 <= each ASCII string length <= 1000.
Example
Input
kitten sitting
Output
3
Example 2 input
ab ba
Output
2
Swapping adjacent characters is not a single allowed edit.
Public test cases (2)
Input
kitten sitting
Expected output
3
Input
horse ros
Expected output
3
Hints (2)
- Identify the state needed to avoid repeated work.
- Build prefix distances and retain only the previous row.
Target complexity: time O(nm + n + m) · space O(min(n, m) + 1)