Edit Distance

Medium · 2-D Dynamic Programming

You are given two strings. You may transform the first string into the second one using a sequence of single-character operations: insert a character, delete a character, or replace a character with another. Return the minimum number of such operations needed to turn the first string into the second string.

Examples

Input:  word1 = "horse", word2 = "ros"
Output: 3
Why:    Remove 'h', replace 'o' with 'r', remove 'e' turns horse into ros in 3 edits, and no shorter sequence exists.

Input:  word1 = "", word2 = "abc"
Output: 3
Why:    The only way to build abc from an empty string is to insert its 3 characters.

Input:  word1 = "same", word2 = "same"
Output: 0
Why:    The strings already match, so zero edits are needed.

Constraints

0 <= word1.length, word2.length <= 500, word1 and word2 consist of lowercase English letters

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Edit Distance

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Edit Distance. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.