Skip to content
RED SAGSkills
hard60 ptsdynamic-programmingstrings

Edit Distance Between Strings

Spell checkers and fuzzy search rank suggestions by edit distance. Given two strings a and b, return the smallest number of single-character operations needed to turn a into b. The allowed operations are inserting a character, deleting a character, and replacing one character with another.

Example 1

Input: a = "horse", b = "ros"
Output: 3
Explanation: horse -> rorse (replace) -> rose (delete) -> ros (delete).

Example 2

Input: a = "kitten", b = "sitting"
Output: 3

Constraints

  • 0 <= a.length, b.length <= 500
  • Lowercase English letters.
Hint 1

Let dp[i][j] be the distance between the first i characters of a and the first j of b.

Hint 2

If the last characters match, dp[i][j] = dp[i-1][j-1]; otherwise take 1 + the minimum of replace, delete and insert.

Good practice for: Backend Developer, AI Engineer (LLM & Generative AI), Data Scientist, Machine Learning Engineer, Full Stack Developer, Automation Test Engineer

Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.