📘

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:

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/0

Run code to see test results.