📘
Levenshtein Distance
Compute the Levenshtein (edit) distance between two strings. The edit distance is the minimum number of single-character operations (insertions, deletions, substitutions) needed to transform one string into another.
Input format:
- Line 1: First string
- Line 2: Second string
Output: An integer (the edit distance).
Example:
Input:
kitten sitting
Output:
3
Reasoning:
Transformations: kitten → sitten (substitute k→s) sitten → sittin (substitute e→i) sittin → sitting (insert g)
Minimum operations: 3
Constraints:
- Strings can be empty
- Operations: insert, delete, substitute (each costs 1)
- Output: Single integer
Editor
Python 3.13.1
Test Results
0/0Run code to see test results.