Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. The allowed operations are insertion, deletion, and substitution. Pattern focus: Edit distance. This is the standard Levenshtein DP formulation.

Input Format

word1 = source string, word2 = target string

Output Format

minimum number of edit operations

Constraints

  • 0 <= word1.length, word2.length <= 1000
  • word1 and word2 contain lowercase English letters.

Examples

Example 1:

Input:

word1 = "horse"
word2 = "ros"

Output:

3

Explanation:

horse -> rorse -> rose -> ros.

Example 2:

Input:

word1 = "intention"
word2 = "execution"

Output:

5

Explanation:

This is the classic edit-distance example.

Loading...
Edit Distance - Dp Strings DSA Problem