Skip to content
BASA DSA

Edit Distance

Medium2-D Dynamic Programming

Return the fewest single-character insertions, deletions and replacements needed to transform word1 into word2.

Example 1

Input
word1 = "horse"
word2 = "ros"
Output
3

Explanation

horse->rorse replaces h, then delete the extra r to get rose and delete e to get ros: three edits.

Example 2

Input
word1 = ""
word2 = "abc"
Output
3

Explanation

Insert a,b,c into the empty string for three edits.

Example 3

Input
word1 = "same"
word2 = "same"
Output
0

Explanation

Identical strings need no edit.

Constraints

  • 0 <= string lengths <= 500
  • Strings contain lowercase English letters

Function contractminDistanceArguments: json, json
Loading draft…
SolutionRuns on your device