Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 72 Edit Distance - Problem Statement

The problem

Find the minimum number of operations to convert word1 into word2.

You can: insert a character, delete a character, or replace a character.

With word1 = "horse", word2 = "ros":

  • horse → rorse (replace 'h' with 'r')
  • rorse → rose (delete 'r')
  • rose → ros (delete 'e')
  • 33 operations.

With word1 = "intention", word2 = "execution":

  • intention → inention (remove 't')
  • inention → enention (replace 'i' with 'e')
  • enention → exention (replace 'n' with 'x')
  • exention → exection (replace 'n' with 'c')
  • exection → execution (insert 'u')
  • 55 operations.

Constraints: 0≤0 \le word1.length, word2.length ≤500\le 500.