Edit Distance

Medium

dynamic-programmingstring

Given strings word1 and word2, return the minimum number of single-character operations (insert, delete, replace) to convert word1 into word2.

Input

Line 1: word1
Line 2: word2

Output: the minimum operation count.

Example 1

Input:

horse
ros

Output:

Example 2

Input:

intention
execution

Output:

Constraints

0 ≤ lengths ≤ 500
Lowercase English letters.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Edit Distance

Medium

dynamic-programmingstring

Given strings word1 and word2, return the minimum number of single-character operations (insert, delete, replace) to convert word1 into word2.

Input

Line 1: word1
Line 2: word2

Output: the minimum operation count.

Example 1

Input:

horse
ros

Output:

Example 2

Input:

intention
execution

Output:

Constraints

0 ≤ lengths ≤ 500
Lowercase English letters.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.