dsa · hard

Edit Distance

StringDynamic Programming

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

Arguments

• word1 — the first word
• word2 — the second word

You have the following three operations permitted on a word: 1. Insert a character 2. Delete a character 3. Replace a character

**Example 1:** `` Input: word1 = "horse", word2 = "ros" Output: 3 ` **Example 2:** ` Input: word1 = "intention", word2 = "execution" Output: 5 ``

Constraints

0 <= word1.length, word2.length <= 500 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
horse
ros

Expected:
3

Example 2

Input:
intention
execution

Expected:
5

Open in the Dojo editor