Problem Description

Find the minimum number of single-character edit operations (insert, delete, or replace) required to transform one string into another. This is known as the Levenshtein distance or edit distance.

Input Format

Two strings on separate lines.

Output Format

Single integer representing the minimum edit distance.

Constraints

• 0 ≤ string length ≤ 1000

• Strings contain only lowercase English letters

• Three operations allowed: insert, delete, replace

• Each operation has cost 1

• Empty strings are allowed

Sample Input/Output

Explanation

Transformations: kitten → sitten (replace k with s), sitten → sittin (replace e with i), sittin → sitting (insert g). Total: 3 operations.