Asked at

Edit Distance

Hard
VerifiedString MatchingDynamic Programming~30 min

Given two strings word1 and word2, return the minimum number of single-character insertions, deletions, or replacements to convert word1 into word2.

The input arrives as a single object { word1, word2 }. Return the operation count.

Examples

in{ word1: "horse", word2: "ros" }
out3

Replace h→r, drop r, drop e.

in{ word1: "intention", word2: "execution" }
out5

Five edits convert one word into the other.

Constraints

  • 0 ≤ word1.length, word2.length ≤ 500
  • Inputs consist of lowercase English letters.
  • Target: O(m · n) time

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.