mafeshsho8lmafeshsho8l
Get Started
All coding questions

Edit Distance

hard
LeetCode Top 100dynamic-programmingstrings

Problem

Given two strings, return the minimum number of single-character insertions, deletions, or substitutions needed to transform the first into the second.

Examples

Input: a = "horse", b = "ros"
Output: 3
Replace h, remove r, remove e.
Input: a = "intention", b = "execution"
Output: 5
Five edits convert one to the other.

Constraints

  • • 0 <= a.length, b.length <= 500
  • • Strings contain lowercase English letters
Hints(tap to reveal)
  • 1. Compare prefixes of the two strings.
  • 2. Matching characters cost nothing; otherwise take the cheapest of three edits.
Optimal approach(spoiler)
  1. Define dist(i, j) as the edit distance between the first i and first j characters.
  2. If the current characters match, carry the diagonal value.
  3. Otherwise take one plus the minimum of insert, delete, and replace neighbours.
  4. Fill the table row by row, base cases being empty prefixes.
  5. O(m * n) time, O(min(m, n)) space with a rolling row.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor